Research map / Graph learning / Graph algorithms and clustering
A Few Moments Please: Scalable Graphon Learning via Moment Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MomentNet, an INR-based graphon estimator trained to match empirical induced motif densities (no latent variables or Gromov-Wasserstein), with a cut-distance bound, and MomentMixup, a moment-space mixup augmentation for graph classification.
Problem
Scalable, resolution-free estimation of graphons from observed graphs; existing INR methods rely on latent variable estimation or costly Gromov-Wasserstein alignment. Also needs better data augmentation for graph classification.
Approach
Train an implicit neural representation so its Monte Carlo induced motif densities match empirical motif densities averaged over observed graphs, avoiding latent variables and GW distances; and perform mixup by interpolating class-wise moment vectors and then generating graphs from the MomentNet-estimated graphon.
Key results
- MomentNet beats SIGL on 9 of 13 graphons by GW loss, per the authors.
- On the graph classification benchmarks, MomentMixup reaches 74.30% on IMDB-B vs 73.95% for G-Mixup w/ SIGL and 98.5% on AIDS vs 98% with no augmentation.
- MomentNet runtime scales more favorably than SIGL, with a clear advantage for n > 300.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MomentMixup instead of G-Mixup with SIGL | GIN · IMDB-B test | accuracy: 73.95$\pm$2.64 -> 74.30$\pm$2.70 | Helped |
| Use MomentMixup instead of G-Mixup with SIGL | GIN · IMDB-M test | accuracy: 50.70$\pm$1.41 -> 50.95$\pm$1.93 | Helped |
| Use MomentMixup instead of G-Mixup with SIGL | GIN · REDD-B test | accuracy: \textbf{92.25}$\pm$1.41 -> 91.8 $\pm$ 1.2 | Hurt |
| Use MomentMixup instead of G-Mixup with USVT | GIN · AIDS test | accuracy: 97.8$\pm$0.9 -> 98.5$\pm$0.6 | Helped |
Surprising findings
- MomentMixup underperforms G-Mixup w/ SIGL on Reddit-Binary (91.8 vs 92.25), which the authors attribute to using only nine motifs.
Limitations
- Performance depends on a pre-selected set of motifs and can degrade if moments are insufficient or noisy.
- Models a single graphon per class, which may not capture heterogeneous graph data.
- The Reddit-Binary result is weaker, attributed to using only nine motifs.
Experimental setup
Datasets: 13 graphon distributions from literature AIDS IMDB-Binary IMDB-Multi Reddit-Binary
Benchmarks: 13 synthetic graphons (graphon estimation) cos-graphon scalability sweep n=10 to 510 AIDS IMDB-B IMDB-M REDD-B
Metrics: Gromov-Wasserstein loss estimation error runtime graph classification accuracy
Baselines: USVT SAS IGNR GWB SIGL G-Mixup
Builds on: IGNR SIGL G-Mixup ORCA Mixup
Closest papers by meaning
- Low-Rank Graphon Learning for Networks (NeurIPS 2025 · similarity 0.90)
- Transfer Learning on Edge Connecting Probability Estimation Under Graphon Model (NeurIPS 2025 · similarity 0.87)
- Temporal Graph Neural Tangent Kernel with Graphon-Guaranteed (NeurIPS 2024 · similarity 0.86)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.86)
- Learning Changes in Graphon Attachment Network Models (ICML 2025 · similarity 0.85)
- DiPhon: Diffusion on Graphons for Scalable Graph Generation (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.