Graphon Mixtures
Sevvandi Kandanaarachchi, Cheng Soon Ong · 2025
Read Graphon Mixtures by Sevvandi Kandanaarachchi, Cheng Soon Ong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13864.txt.
Introduction
Sevvandi Kandanaarachchi and Cheng Soon Ong model networks as blends of sparse and dense graphons. Their 2025 paper starts from a pattern in social networks: a few huge hubs amid many small tight communities. One smooth model rarely captures both shapes at once.
Their mixture model builds each graph from sparse and dense parts. A new cap on node degree in the sparse part lets hubs be picked out cleanly. Theory shows the hub sizes and the sparse pattern can both be estimated from data. Tests on synthetic graphs, citation networks, and social data show the gain. The authors argue sparse parts deserve direct modelling.
Catalog record
| CREATOR | Sevvandi Kandanaarachchi, Cheng Soon Ong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 134 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13864
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graphon Mixtures Sevvandi Kandanaarachchi, Cheng Soon Ong Abstract Social networks have a small number of large hubs, and a large number of small dense communities. We propose a generative model that captures both hub and dense structures. Based on recent results about graphons on line graphs, our model is a graphon mixture, enabling us to generate sequences of graphs where each graph is a combination of sparse and dense graphs. We propose a new condition on sparse graphs (the max-degree), which enables us to identify hubs. We show theoretically that we can estimate the normalized degree of the hubs, as well as estimate the graphon corresponding to sparse components of graph mixtures. We illustrate our approach on synthetic data, citation graphs, and social networks, showing the benefits of explicitly modeling sparse graphs. 1 Introduction Edge density is a graph attribute that helps to characterize graph sequences into dense or sparse graphs. A graph sequence is called dense if the edges grow quadratically with the nodes, and it is called sparse if the edges grow sub-quadratically with the nodes. A characteristic of dense graphs is that nodes are more connected to each other. A characteristic of sparse graphs is that they are less connected. Simple examples of sparse graphs include stars, paths and rings. Observed sparse graphs such as social networks exhibit two contrasting types of behavior: a small number of high degree nodes called hubs inducing sparsity and a large number of small, dense communities ( Zang et al., 2018 ; Zhao et al., 2021 ) . Such hubs and communities are also observed in complex multi-functional networks such as neurological networks ( Van den Heuvel & Sporns, 2013 ; Schwarz et al., 2008 ) . A hub, viewed in isolation can be thought of as a star graph and a community by itself can be thought of as a dense graph. The prevalence of these two components in both biological and social networks is evidence that they are fundamental structures in evolving graphs. Motivated by these considerations we consider graph mixtures – a combination of two graphs, one sparse and one dense generated from two different types of graph generators: graphons. A graphon is a symmetric and measurable function W:[0,1]^{2}\rightarrow[0,1] . Graphons are used to learn the underlying structure or representation of graphs ( Xu et al., 2021 ) and recently graphons are used in neural operators and graph neural networks ( Levie, 2023 ; Tieu et al., 2024 ; Cheng & Peng, 2023 ) . A graphon can be thought of as a graph blueprint and can be used to generate graphs of an arbitrarily large size. As a consequence of the Aldous-Hoover theorem ( Aldous, 1981 ) , graphs generated from a graphon W are dense. Thus, while it straightforward to generate dense graphs from a graphon W , generating sparse graphs from a graphon is not quite that simple. There have been several extensions to graphons to model sparse graphs. Caron et al. (2023) model graphs as exchangeable point processes and extend the classical graphon framework to the sparse regime. Their graphons are defined on \mathbb{R}_{+}^{2} instead of on the unit square [0,1]^{2} . Research led by Borgs and Chayes tackle sparsity in different ways. For example, Borgs et al. (2018) consider ‘stretched’ and ‘rescaled’ graphons that can represent sparse graphs. Veitch & Roy (2015) introduce graphexes, a triple describing isolated edges, infinite stars and a graphon defined on \mathbb{R}_{+}^{2} . Kandanaarachchi & Ong (2024) model sparse graphs by considering graphons of line graphs. We use results from Kandanaarachchi & Ong (2024) and Janson (2016) to define graphon mixtures, which can generate sparse and dense graphs depending on the mixture properties. Our approach for sparse graph generation considers line graphs. Line graphs, also known as non-backtracking graphs ( Krzakala et al., 2013 ) are obtained by mapping edges to vertices. A line graph of a graph G_{n} denoted by L(G_{n}) maps edges of G_{n} to vertices of L(G_{n}) and connects vertices in L(G_{n}) if the corresponding edges in G_{n} share a vertex (Figure 1(a) ). Kandanaarachchi & Ong (2024) showed that for a subset of sparse graphs, which they called square-degree , the line graphs are dense. Hence, for square-degree graphs, by taking line graphs, we are back in the space of dense graphs which we know how to model using the standard graphon. However, this hardly tells us anything about the structure of the line graph graphon. Janson (2016) showed that line graph limits are disjoint clique graphs and further showed that disjoint clique graphs can be modelled by a sequence of positive numbers, which he called a mass-partition . This result combined with the inverse line graph operation enable us to define graphon mixtures. The contributions of this paper are: (1) we propose graphon mixtures – a novel approach that explicitly models sparsity and thereby generates graph mixtures; (2) given a graph mixture, we estimate the degree of hubs of unseen graphs and the graphon corresponding to the sparse components, and we provide theoretical guarantees on our estimates that have exponential or polynomial convergence; (3) we show empirically that our approach is useful on synthetic and real data. All proofs are presented in the Appendix. 2 Limits of sparse graphs and line graphs We review the setting of graphons, in particular with respect to the recent results on graphons on line graphs ( Kandanaarachchi & Ong, 2024 ) . Definition 2.1 ( Dense and sparse graph sequences). A sequence of graphs \{G_{n}\}_{n} is dense if the number of edges m grow quadratically with the number of nodes n , i.e., \liminf_{n\to\infty}\frac{m}{n^{2}}=c>0\,. A sequence of graphs \{G_{n}\}_{n} is sparse if the number of edges m grow sub-quadratically with the number of nodes n , i.e., \lim_{n\to\infty}\frac{m}{n^{2}}=0\,. A graphon is a symmetric and measurable function W:[0,1]^{2}\rightarrow[0,1] . Graphs and graphons are linked by the adjacency matrix. The empirical graphon (Definition A.2 ) of a graph is obtained by scaling the adjacency matrix to the unit square and coloring smaller squares of size 1/n\times 1/n black if the corresponding entry in the adjacency matrix is 1 and coloring it white if the entry is 0. Given a graphon W , a graph with n nodes for any n\in{\mathbb{N}} can be generated as follows: Definition 2.2 . Uniformly pick x_{1},x_{2},\ldots x_{n} from [0,1] . A W-random graph \mathbb{G}(n,W) has the vertex set 1,2,\ldots n and vertices i and j are connected with probability W(x_{i},x_{j}) . Given a sequence of graphs \{G_{n}\}_{n} , convergence is defined using the cut norm (Definition A.3 ) and the cut metric (Definition A.4 ). Borgs et al. (2008) showed that every convergent graph sequence converges to a graphon W . Therefore, graphons are graph limits. The problem is that all sparse graph sequences converge to W=0 . Hence, the standard graphon is not representative of sparse graphs, in the sense that graphs generated from W=0 are isolated nodes without any edges. 2.1 Sparse graphs are stars in the limit ((a)) ((b)) Figure 1 : (a) A graph G and its line graph L(G) . Vertices in L(G) are edges of G . Vertices of L(G) are connected if the corresponding edges in G