Graphons of Line Graphs

Sevvandi Kandanaarachchi; Cheng Soon Ong

stat.MLSep 3, 2024

Graphons of Line Graphs

Authors: Sevvandi Kandanaarachchi, Cheng Soon Ong

Abstract

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.

Figures & tables

Figure 1: Top row: Graphs of 1 to 4 disjoint stars. Recall the graphon

W=0

for star graphs. Middle row: Line graphs of disjoint stars in top row. Line graphs of star graphs are complete graphs. Bottom row: The graphons of the line graphs of the star graphs (taken as sequences) shown on top.

Panel of Figure 2 — Figure 2: Characterization of graph sequences $\{G_{n}\}_{n}$ with results discussed in this paper in blue text. $\{G_{n}\}_{n}\in S_{q}$ indicates that the graph sequence satisfies the square-degree property. If $\{G_{n}\}_{n}$ converges to $W$ , then for dense graphs $\{G_{n}\}_{n}$ , $W\neq 0$ , but $U=0$ . Recall that sparse graphs converge to $W=0$ . For sparse $\{G_{n}\}_{n}\notin S_{q}$ we have $U=0$ . However if $\{G_{n}\}_{n}\in S_{q}$ and $\{H_{m}\}_{m}$ converges to $U$ , then $U\neq 0$ . Depending on the mixture properties $(U,W)$ -mixture graphs can be dense, sparse or square-degree.

Figure 3: A graph on the left and its line graph on the right.

Figure 4: Graphons $W_{1}$ , $W_{2}$ and $W_{\text{sum}}=0.6W_{1}\oplus 0.4W_{2}$ .

Figure 5: Vertex and edge exchangeability in graphs and line graphs. Graphs

G

and

H=L(G)

on the top row. Graph

H^{\prime}

is a vertex permuted version of

H

. We see that

H^{\prime}=L(G^{\prime})

, where

G^{\prime}

is the edge permuted version of

G

Panel of Figure 6 — Figure 6: The Euler diagram of the space of dense and sparse graph sequences, and indicate where there are graph sequences satisfying the square-degree property. The set $S\backslash S_{q}$ is non-empty as paths $\{P_{n}\}_{n}$ , cycles $\{C_{n}\}_{n}$ and other graphs live here. The line graphs $\{H_{m}\}_{m}$ are dense in the shaded set $S_{q}$ .

Panel of Figure 7 — Figure 7: The Euler diagram in Figure 6 updated for converging $\{G_{n}\}_{n}$ and $\{H_{m}\}_{m}$ .

Panel of Figure 8 — Figure 8: The map from converging $\{G_{n}\}_{n}$ to converging $\{H_{m}\}_{m}$ , summarising Lemmas 4.2 , 4.3 and 4.4 .

Panel of Figure 9 — Figure 9: The Euler diagram in Figure 7 updated with a subset of $(U,W)$ -mixture graphs.

Graphon Theory

See all 9 papers

Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index
Aug 14, 2026Jian Xu, Delu Zeng, John Paisley +1
RIKEN iTHEMS, Wako, Japan · RIKEN Center for Advanced Intelligence Project (AIP), Tokyo, Japan · South China University of Technology, Guangzhou, China +1
Attention Graphons: A Graph Limit Perspective on Graph Transformers
Sep 28, 2026Caio F. Deberaldini Netto, Moshe Eliasof, Luana RuizGraphon Theory Transformer Attention
Johns Hopkins University Baltimore, MD · University of Cambridge Cambridge, UK
Recovery thresholds for hidden weighted sparse graphs
Jun 12, 2026Zhe Hou, Jingcheng LiuGraph Structure Learning Information-Theoretic Lower Bounds
State Key Laboratory for Novel Software Technology, Nanjing University

Aug 14, 2026J/K move · Enter open · S save

Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index

Jian Xu, Delu Zeng, John Paisley, Qibin Zhao

RIKEN iTHEMS, Wako, Japan · RIKEN Center for Advanced Intelligence Project (AIP), Tokyo, Japan · South China University of Technology, Guangzhou, China+1

Open paper AskPDF arXiv

A large graph is often available only in part: a crawl stopped by its budget, a panel, a partial dump. When the sampled fraction

s

is known by design the total edge count follows from

\hat e=e_s/s^2

and no model is needed. We treat the case where

s

is unknown and the population size is known. Our main result is a reduction: under a sparse exchangeable (graphex) model the expected non-isolated fraction obeys

n_s/n_1\to s^{1+σ}

, so the sampling rate becomes estimable once the tail index

σ

is, and substituting it back gives

e_s(n_1/n_s)^{2/(1+σ)}

-- the same estimator, with the design quantity inferred. Estimating global edge cardinality in a sparse graph is therefore, in expectation, tail-index estimation, and the quadratic graphon estimator is the case

σ=0

: it fails by an identity rather than by a fit (

260\%

median error against

27\%

). We bound the finite-size error of the substitution and show the reduction is modular in the tail-index estimator --- filled with a published closed-form one it reaches

21.7\%

over

13

networks and

39

sampling budgets with no fitting at all. Fitting a full graphex additionally returns the degree distribution at any size and a generative object, in a representation where sparsity is a coordinate and the interpolation path is dictated rather than chosen. Two limits are exact: rank-one graphexes have transitivity fixed by the degree profile, so high-clustering graphs lie outside the class; and under snowball or random-walk crawls every method here fails, the design-based oracle worst of all (

7.8\%

588\%

Abstract

Graphon Theory

Explore similar work

Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index

Attention Graphons: A Graph Limit Perspective on Graph Transformers

Recovery thresholds for hidden weighted sparse graphs