Graphons for Machine Learning: Theory, Estimation, and Applications

← Back to Teaching

Event: NeurIPS 2026 Education Track Authors: Sevvandi Kandanaarachchi, Cheng Soon Ong Date and location: Monday 7 December 2026, Sydney, Australia

Concept

Graphons are graph limits. Traditionally a graphon is defined on a unit square as $W:[0,1]^2 \to [0,1]$ with the output denoting the edge probability. They capture the asymptotic structure of a graph in a size-independent form, enabling graphs of different sizes to be studied and compared within a unified framework.

Graphons are increasingly used in machine learning: for GNN transferability across graphs of different sizes, and for neural network pruning, among other applications. Estimating a graphon from observed graph data is itself an active research problem, with newer approaches, such as IGNR and JGS, offering more flexible, learnable alternatives to classical estimators. At the same time, while a rich body of theory has been developed for sparse graphons and related extensions, these models have seen relatively limited adoption within machine learning, despite the prevalence of sparse graphs in real-world applications.

Together, this combination of graphons’ growing role in core ML tasks, a rapidly evolving landscape of estimation methods, and the largely untapped potential of sparse graphon models motivates their inclusion in the NeurIPS 2026 Education Track. This tutorial covers some applications and emerging opportunities for leveraging graphons in machine learning.

Prerequisites: basic graph theory, linear algebra and calculus.

Learning Objectives and Outcomes

On completion of this mini-course, participants will be able to:

  1. understand the mathematical foundations of graphons, including homomorphism densities, cut distance/cut norm, convergence and exchangeability,

  2. apply graphons as a base generative model to generate graphs, and combine graphons to construct richer and more complex network structures,

  3. understand the limitations of classical graphons for modelling sparse graphs, and gain hands-on experience with sparse graph extensions covering Kallenberg exchangeable graphs, graphon mixtures, and graphettes,

  4. evaluate and understand graphon estimation methods, including traditional methods such as SAS and more recent methods such as Implicit Graphon Neural Representation (IGNR) and the Joint Graph Sorting (JGS) estimator,

  5. understand and describe how graphons are used in machine learning, for example in GNN transferability and neural network pruning.

Recent papers using graphons in Machine Learning (at the time of writing)

  1. Cheng, H., Chen, Y., Ma, P. and Zhong, W. (2026). Graphon Cross-Validation: Assessing Models on Network Data. In The Fourteenth International Conference on Learning Representations. Link

  2. Fan, X., Ma, F., Leng, C. and Wu, W. (2025). Low-Rank Graphon Learning for Networks. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. Link

  3. Pham, H., Ta, T.-A., Jacobs, T., Burkholz, R. and Tran-Thanh, L. (2025). The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.Link

  4. Wang, Y., Cheng, Y.-H., Mukherjee, D. and Cheng, H. (2025). Transfer Learning on Edge Connecting Probability Estimation Under Graphon Model. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.Link

Teaching Materials

Teaching materials consist of videos, slides and Jupyter worksheets detailed as follows:

Part 1: Introduction to graphons

This video introduces graphons as a generative model and samples graphs from different graphons. It combines graphons in 3 different ways: convex addition, disjoint union and joining disjoint graphons.

Part 2: Mathematical properties of graphons

Mathematical properties of graphons: This video introduces graphons as graph limits and explores convergence from the lens of homomorphism density and the cut metric. Furthermore, it briefly discusses the assumption of exchangeability.

Part 3: Some approaches for sparse graphs

Sparse graph modelling with graphons: This video explores different sparse extensions of traditional graphons.

These 3 worksheets explore different graphon-related sparse graph generation mechanisms including Kallenberg exchangeable graphs detailed in Caron and Fox (2017).

Part 4: Graphon estimation

Graphon estimation: This video introduces graphon estimation when a single graph or multiple graphs are observed.

These 2 worksheets explores graphon estimation using IGNR (Xia et al, 2023) and JGS (Sogan and Rebafka, 2026).

Part 5: Graphons in machine learning

Graphons in machine learning: This video discusses 2 applications of graphons – GNN transferability and neural network pruning.

Jupyter Worksheets

  1. Introduction to graphons: This worksheet introduces graphon sampling and combines graphons in 3 different ways: convex addition, disjoint union and joining disjoint graphons. Open in Colab · Download

  2. Kallenberg exchangeable graphs (Caron and Fox, 2017): Open in Colab · Download

  3. Graphon mixtures: Open in Colab · Download

  4. Graphettes: Open in Colab · Download

  5. Graphon estimation with IGNR: Open in Colab · Download

  6. Graphon estimation with JGS: Open in Colab · Download

Downloads

Acknowledgements

The Jupyter worksheets were developed with assistance from Anthropic’s Claude. The first author reviewed, tested and is responsible for all content. The code in Caron_Fox_BNPGraph.py is a Python port of the MATLAB BNPgraph package by Francois Caron, created with the help of Claude. It follows Caron and Fox (2017).

References

  1. Borgs, C., Chayes, J. T., Cohn, H. and Holden, N. (2018). Sparse exchangeable graphs and their limits via graphon processes. Journal of Machine Learning Research, 18(210), 1-71. Link

  2. Caron, F. and Fox, E. B. (2017). Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society: Series B, 79(5), 1295-1366. Link

  3. Kandanaarachchi, S. and Ong, C. S. (2026). Graphon mixtures. In Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:514-522. Link

  4. Lovász, L. (2012). Large Networks and Graph Limits. American Mathematical Society. Link

  5. Pham, H., Ta, T.-A., Jacobs, T., Burkholz, R. and Tran-Thanh, L. (2025). The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis. In Advances in Neural Information Processing Systems 38 (NeurIPS 2025). Link

  6. Ruiz, L., Chamon, L. and Ribeiro, A. (2020). Graphon Neural Networks and the Transferability of Graph Neural Networks. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020). Link

  7. Sogan, R. B. and Rebafka, T. (2026). Low-Complexity and Consistent Graphon Estimation from Multiple Networks. In Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1441-1449. Link

  8. Wijesinghe, A., Kandanaarachchi, S., Steinberg, D. M. and Ong, C. S. (2026). Flowette: Flow Matching with Graphette Priors for Graph Generation. In The Fortieth Annual Conference on Neural Information Processing Systems (NeurIPS 2026). Link

  9. Xia, X., Mishne, G. and Wang, Y. (2023). Implicit Graphon Neural Representation. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:10619-10634. Link