# Graphons of Line Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 3 Sep 2024.

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

- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures](https://mlsanity.com/paper/1312.7857/) (2013)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [The Class of Random Graphs Arising from Exchangeable Random Measures](https://mlsanity.com/paper/1512.03099/) (2015)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [Edge-exchangeable graphs and sparsity](https://mlsanity.com/paper/1603.06898/) (2016)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [Sampling random graph homomorphisms and applications to network data analysis](https://mlsanity.com/paper/1910.09483/) (2019)

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

- [DiPhon: Diffusion on Graphons for Scalable Graph Generation](https://mlsanity.com/paper/2607.07232/) (2026)

## Abstract (arXiv)

We consider the problem of estimating graph limits, known as graphons, from observations of sequences of sparse finite graphs. In this paper we show a simple method that can shed light on a subset of sparse graphs. The method involves mapping the original graphs to their line graphs. We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs. This enables the use of results on graph limits of dense graphs to derive convergence. In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs. We demonstrate empirically that we can distinguish different numbers of stars (which are sparse) by the graphons of their corresponding line graphs. Whereas in the original graphs, the different number of stars all converge to the zero graphon due to sparsity. Similarly, superlinear preferential attachment graphs give rise to dense line graphs almost surely. In contrast, dense graphs, including Erdos-Renyi graphs make the line graphs sparse, resulting in the zero graphon.