# Low-Complexity and Consistent Graphon Estimation from Multiple Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 52 references that are in the map.
- First posted on arXiv 16 Mar 2026.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Implicit Neural Representations with Periodic Activation Functions](https://mlsanity.com/paper/2006.09661/) (2020)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Stochastic blockmodel approximation of a graphon: Theory and consistent estimation](https://mlsanity.com/paper/1311.1731/) (2013)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Learning Graphons via Structured Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2012.05644/) (2020)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [GraphMAD: Graph Mixup for Data Augmentation using Data-Driven Convex Clustering](https://mlsanity.com/paper/2210.15721/) (2022)
- [Graphons, mergeons, and so on!](https://mlsanity.com/paper/1607.01718/) (2016)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Modeling heterogeneity in random graphs through latent space models: a selective review](https://mlsanity.com/paper/1402.4296/) (2014)
- [EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches](https://mlsanity.com/paper/1903.06936/) (2019)
- [Learning common structures in a collection of networks. An application to food webs](https://mlsanity.com/paper/2206.00560/) (2022)

## Abstract (arXiv)

Recovering the random graph model from an observed collection of networks is known to present significant challenges in the setting, where the networks do not share a common node set and have different sizes. More specifically, the goal is the estimation of the graphon function that parametrizes the nonparametric exchangeable random graph model. Existing methods typically suffer from either limited accuracy or high computational complexity. We introduce a new histogram-based estimator with low algorithmic complexity that achieves high accuracy by jointly aligning the nodes of all graphs, in contrast to most conventional methods that order nodes graph by graph. Consistency results of the proposed graphon estimator are established. A numerical study shows that the proposed estimator outperforms existing methods in terms of accuracy, especially when the dataset comprises only small and variable-size networks. Moreover, the computing time of the new method is considerably shorter than that of other consistent methodologies. Additionally, when applied to a graph neural network classification task, the proposed estimator enables more effective data augmentation, yielding improved performance across diverse real-world datasets.