Graphon estimation in bipartite networks
Estimation de graphon pour les graphes bipartis
Résumé
Many real-world datasets can be represented as matrices where the entries represent interactions between two entities of different natures. These matrices are commonly known as adjacency matrices of bipartite graphs. In our work, we make the assumption that these interactions are determined by unobservable latent variables.Firstly, our main objective is to estimate the conditional expectation of the data matrix given the unobservable variables under the assumption that matrix entries are i.i.d. This estimation problem can be framed as estimating a bivariate function known as a graphon. In our study, we focus on two cases: piecewise constant graphons and Hölder-continuous graphons.We derive finite sample risk bounds for the least squares estimator. Additionally, we propose an adaptation of Lloyd's algorithm to compute an approximation this estimator and provide results from numerical experiments to evaluate the performance of these methods.Secondly, we address the limitations of the previous framework, which may not be suitable for modeling situations with bounded degrees of vertices, among other scenarios. Therefore, we extend our study to the relaxed independence assumption, where only the rows of the adjacency matrix are assumed to be independent. In this context, we specifically focus on piecewise constant graphons.
De nombreux ensembles de données peuvent être représentés sous forme d'une matrice dont les entrées représentent les interactions entre deux entités de natures différentes. Ces matrices sont appelées matrices d'adjacence de graphes bipartites. Dans notre travail, nous faisons l'hypothèse que ces interactions sont déterminées par des variables latentes non observables.Dans un premier temps, notre objectif est d'estimer l'espérance conditionnelle de la matrice de données sachant les variables non observables, en supposant que les entrées de la matrice sont i.i.d. Ce problème peut être formulé comme l'estimation d'une fonction bivariée appelée graphon. Dans notre étude, nous nous concentrons sur deux cas, les graphons constants par morceaux et les graphons Hölder.Nous démontrons des bornes de risque pour l'estimateur des moindres carrés, et nous proposons une adaptation de l'algorithme de Lloyd pour calculer une approximation de cet estimateur et nous présentons les résultats d'expériences numériques pour évaluer les performances de ces méthodes.Dans un deuxième temps, nous abordons les limites du cadre précédent, qui peut ne pas être adapté pour modéliser des situations avec des degrés de sommet bornés. Par conséquent, nous étendons notre étude à l'hypothèse de l'indépendance relaxée, où seules les lignes de la matrice d'adjacence sont supposées indépendantes. Dans ce contexte, nous nous concentrons spécifiquement sur les graphons constants par morceaux.
Origine : Version validée par le jury (STAR)