# A Few Moments Please: Scalable Graphon Learning via Moment Matching

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 4 Jun 2025.

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

- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [Implicit Neural Representations with Periodic Activation Functions](https://mlsanity.com/paper/2006.09661/) (2020)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Learning Smooth Neural Functions via Lipschitz Regularization](https://mlsanity.com/paper/2202.08345/) (2022)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [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)
- [Centrality measures for graphons: Accounting for uncertainty in networks](https://mlsanity.com/paper/1707.09350/) (2017)
- [Robust Graph Filter Identification and Graph Denoising from Signal Observations](https://mlsanity.com/paper/2210.08488/) (2022)
- [GraphMAD: Graph Mixup for Data Augmentation using Data-Driven Convex Clustering](https://mlsanity.com/paper/2210.15721/) (2022)
- [Graphon Control of Large-scale Networks of Linear Systems](https://mlsanity.com/paper/1807.03412/) (2018)
- [Network Topology Inference with Graphon Spectral Penalties](https://mlsanity.com/paper/2010.07872/) (2020)
- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Redesigning graph filter-based GNNs to relax the homophily assumption](https://mlsanity.com/paper/2409.08676/) (2024)
- [Tracking Network Dynamics using Probabilistic State-Space Models](https://mlsanity.com/paper/2409.08238/) (2024)

## Built on by (most cited first, 3 of 3)

- [NGDB-Zoo: Towards Efficient and Scalable Neural Graph Databases Training](https://mlsanity.com/paper/2602.21597/) (2026)
- [From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning](https://mlsanity.com/paper/2510.03690/) (2025)
- [Attention Graphons: A Graph Limit Perspective on Graph Transformers](https://mlsanity.com/paper/2609.35620/) (2026)

## Abstract (arXiv)

Graphons, as limit objects of dense graph sequences, play a central role in the statistical analysis of network data. However, existing graphon estimation methods often struggle with scalability to large networks and resolution-independent approximation, due to their reliance on estimating latent variables or costly metrics such as the Gromov-Wasserstein distance. In this work, we propose a novel, scalable graphon estimator that directly recovers the graphon via moment matching, leveraging implicit neural representations (INRs). Our approach avoids latent variable modeling by training an INR--mapping coordinates to graphon values--to match empirical subgraph counts (i.e., moments) from observed graphs. This direct estimation mechanism yields a polynomial-time solution and crucially sidesteps the combinatorial complexity of Gromov-Wasserstein optimization. Building on foundational results, we establish a theoretical guarantee: when the observed subgraph motifs sufficiently represent those of the true graphon (a condition met with sufficiently large or numerous graph samples), the estimated graphon achieves a provable upper bound in cut distance from the ground truth. Additionally, we introduce MomentMixup, a data augmentation technique that performs mixup in the moment space to enhance graphon-based learning. Our graphon estimation method achieves strong empirical performance--demonstrating high accuracy on small graphs and superior computational efficiency on large graphs--outperforming state-of-the-art scalable estimators in 75% of benchmark settings and matching them in the remaining cases. Furthermore, MomentMixup demonstrated improved graph classification accuracy on the majority of our benchmarks.