# Graphon based Clustering and Testing of Networks: Algorithms and Theory

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 6 Oct 2021.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [The Multiscale Laplacian Graph Kernel](https://mlsanity.com/paper/1603.06186/) (2016)
- [Estimating network edge probabilities by neighborhood smoothing](https://mlsanity.com/paper/1509.08588/) (2015)
- [Temporal Graph Kernels for Classifying Dissemination Processes](https://mlsanity.com/paper/1911.05496/) (2019)
- [Two-sample Hypothesis Testing for Inhomogeneous Random Graphs](https://mlsanity.com/paper/1707.00833/) (2017)
- [On clustering network-valued data](https://mlsanity.com/paper/1606.02401/) (2016)
- [Two-Sample Tests for Large Random Graphs Using Network Statistics](https://mlsanity.com/paper/1705.06168/) (2017)
- [Practical methods for graph two-sample testing](https://mlsanity.com/paper/1811.12752/) (2018)
- [Provable Estimation of the Number of Blocks in Block Models](https://mlsanity.com/paper/1705.08580/) (2017)
- [Near-Optimal Comparison Based Clustering](https://mlsanity.com/paper/2010.03918/) (2020)

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

- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks](https://mlsanity.com/paper/2311.15598/) (2023)
- [The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis](https://mlsanity.com/paper/2510.17515/) (2025)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [Graphons of Line Graphs](https://mlsanity.com/paper/2409.01656/) (2024)
- [Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2605.25452/) (2026)
- [Two-Sample Testing for Random Graphs without Vertex Correspondence](https://mlsanity.com/paper/2610.07503/) (2026)

## Abstract (arXiv)

Network-valued data are encountered in a wide range of applications and pose challenges in learning due to their complex structure and absence of vertex correspondence. Typical examples of such problems include classification or grouping of protein structures and social networks. Various methods, ranging from graph kernels to graph neural networks, have been proposed that achieve some success in graph classification problems. However, most methods have limited theoretical justification, and their applicability beyond classification remains unexplored. In this work, we propose methods for clustering multiple graphs, without vertex correspondence, that are inspired by the recent literature on estimating graphons -- symmetric functions corresponding to infinite vertex limit of graphs. We propose a novel graph distance based on sorting-and-smoothing graphon estimators. Using the proposed graph distance, we present two clustering algorithms and show that they achieve state-of-the-art results. We prove the statistical consistency of both algorithms under Lipschitz assumptions on the graph degrees. We further study the applicability of the proposed distance for graph two-sample testing problems.