Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - Université de Rouen Normandie

Recovering a random graph model from an observed collection of networks is a challenging task, particularly when the networks do not share a common node set and may have different sizes. In this setting, the objective is to estimate the graphon function underlying a nonparametric exchangeable random graph model. Existing approaches often face a trade-off between statistical accuracy and computational complexity. We introduce a new histogram-based graphon estimator with low algorithmic complexity that achieves high accuracy by jointly aligning the nodes across all networks, in contrast to conventional methods that perform node ordering independently for each graph. We establish consistency results for the proposed estimator. Numerical experiments demonstrate that our method outperforms existing approaches in terms of accuracy, especially when only small and variable-size networks are available, while also significantly reducing computational time compared to other consistent methods. Finally, when applied to a graph neural network classification task, the proposed estimator enables more effective data augmentation and leads to improved performance on several real-world datasets.