Graphons are graph limits. A graphon is a symmetric, measureable function defined on a unit square. They can be used as a generative model for dense graphs. This is the fundamental limitation of graphons; they cannot generate sparse graphs. This set of papers extend graphons to generate sparse graphs.
Graphons of line graphs
Authors: Sevvandi Kandanaarachchi, Cheng Soon Ong Graphons of line graphs TLDR: This paper shows that for a subset of sparse graphs, their line graphs are dense. As such, modeling the graphon of line graphs is useful for a subset of sparse graphs.
Top row: Graphs of 1 to 4 disjoint stars. 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.How do we understand the large graphs that are too sparse for classical tools to handle? This paper tackles that question by introducing a surprising transformation: rather than analysing the graphs directly, we map them to their *line graphs* — where edges become nodes — and then estimate the graphon. The key insight is that certain sparse graphs, those satisfying a certain property, which we call the "square-degree property", produce dense line graphs, making the standard graphon estimation techniques suddenly applicable. Star graphs are a clean example: they are sparse, yet their line graphs are dense cliques, yielding meaningful, non-zero graphons that can distinguish between. For example, networks with different numbers of star-shaped hubs, all collapse to the trivial zero graphon when working with the original graphs. But when we model as line graphs they become dense. The method also extends to superlinear preferential attachment graphs, a common model for real-world growing graphs. The work opens a new pathway for analysing a class of sparse graphs using the rich theory of dense graph limits.
Graphon mixtures
Authors: Sevvandi Kandanaarachchi, Cheng Soon Ong Graphon mixtures Venue: AISTATS 2026 (Accepted) TLDR: This paper proposes a generative method to generate dense or sparse graphs using a mixture of graphons where the sparse graphs are modelled using the inverse line graph.
The overview of (U,W)-mixture graphs. A disjoint clique graph is sampled from the graphon U. The inverse line graph is a disjoint set of stars. A graph is sampled from the graphon W. Then it is joined with the star graphs resulting in a mixture graph.Real-world networks (social networks for example) have a distinctive dual character: a small number of highly connected hubs sitting alongside a large number of tight, dense communities. Existing generative models tend to handle one or the other, but not both. This paper introduces a **graphon mixture model** that explicitly captures this duality by combining sparse and dense graph components within a single unified framework, building on recent results about graphons of line graphs. A key theoretical contribution is a new condition on sparse graphs — the *max-degree condition* — which allows hubs to be identified and their connectivity structure to be estimated. The paper further shows that the graphon corresponding to the dense community component can also be recovered from the mixture. Experiments on synthetic data, citation networks, and social networks demonstrate that explicitly modelling the sparse hub structure, rather than folding everything into a single dense graphon, leads to better representations of the graphs we actually encounter in practice.
Flowette: Flow matching with graphette priors for graph heneration
Authors: Asiri Wijesinghe, Sevvandi Kandanaarachchi, Daniel M. Steinberg, Cheng Soon Ong Flowette: Flow matching with graphette priors TLDR: This paper is on generative modeling of graphs with recurring subgraph motifs. Flowette is a continuous flow matching framework using graphettes, a new probabilistic family of graph structure models.
Flowette training scheme. FGW optimal transport with Hungarian matching, GNN Transformer, Topology-aware loss and regularisation and graphettes.Many real-world graphs — from molecular structures to social networks — are built from recurring patterns such as rings, stars, and tree-like substructures. This paper introduces Flowette, a generative model for graphs that is designed to capture exactly these kinds of structural motifs. At its core, Flowette uses flow matching, a continuous generative modelling approach, guided by a graph neural network transformer that learns how graphs evolve from noise to structured outputs. To encode domain knowledge about recurring substructures, the paper introduces graphettes, a new family of probabilistic graph models that extend the classical graphon framework by allowing controlled structural edits to build in motifs directly. Topology is preserved during generation through optimal transport coupling, and long-range structural dependencies are handled via regularisation. Tested on both synthetic benchmarks and small-molecule generation tasks, Flowette consistently outperforms baselines, making a compelling case that pairing structural priors with flow-based training is a natural and effective recipe for learning complex graph distributions.
A pseudo-inverse of a line graph
Authors: Sevvandi Kandanaarachchi, Phil Kilby, Cheng Soon Ong A pseudo-inverse of a line graph TLDR: This paper is somewhat different in the sense it is not about graph generation. It is about proposing an inverse to the non-invertible line graph operation in terms of a pseudo-inverse.
The setting of a line graph pseudo-inverse.The line graph transformation — which converts a graph's edges into vertices — is a useful tool in graph theory, but it has a fundamental limitation: it is not invertible. Not every graph is a valid line graph, and even when one is, recovering the original root graph from it is non-trivial. This paper tackles the natural question of what happens when a line graph is slightly corrupted or perturbed: can we still recover a valid root graph? This paper frames this as a pseudo-inverse problem and propose a linear integer program that makes the minimum number of edge edits to a given graph until it becomes a valid line graph, at which point the root graph can be recovered. They use the spectral norm to show theoretically that this pseudo-inverse operation is well-behaved — small perturbations in the line graph lead to small, controlled changes in the recovered root graph. Experiments on Erdős-Rényi graphs confirm that the theory holds up in practice, laying groundwork for robust root graph reconstruction in noisy real-world settings.
