Title: From Dense to Sparse: Graphon Mixing for Graph Generation

Speaker: Sevvandi Kandanaarachchi
Commonwealth Scientific and Industrial Research Organisation (CSIRO) 

Summary:

Graphons are graph limits, and can be used to generate new graphs with desired properties. Intuitively, a graphon can be obtained by scaling the adjacency matrix to the unit square and taking its limit. However, as a result of the Aldous-Hoover theorem, traditional graphons can only represent dense graphs, because sparse graphs converge to the zero graphon.  Notwithstanding this challenge, several approaches have been proposed to model sparse graphs, often relying on sophisticated mathematical machinery. 

In this talk we present a simple construction to generate sparse graphs using line graphs. Line graphs map edges to vertices.  We show that a subset of sparse graphs has dense line graphs, allowing them to be modelled via the graphon of their line graphs. Furthermore, we propose a mixture that combines a dense graph sequence generated from a standard graphon W, with a sparse graph sequence generated from a line graph graphon U. This (U,W) mixture can generate both sparse and dense graphs depending on the mixture properties. In addition, sparse graphs generated by the (U,W) mixture matches the structure of many real-world graphs including social networks featuring large hubs alongside tightly knit communities.     

Bio:
Sevvandi Kandanaarachchi is an applied mathematician working in statistical machine learning. She is a Senior Research Scientist at CSIRO and an Associate Investigator at OPTIMA. She has a PhD in Mathematics from Monash University and a Graduate Certificate in Data Mining and Applications from Stanford. Her research focuses on graph and network analysis, algorithm evaluation, and anomaly detection, with active contributions to interdisciplinary projects.  

—

This event is hybrid: no registration needed
PLEASE JOIN IN-PERSON – Level 7, Room 7320 (Board Room), Melbourne Connect, 700 Swanston St, Carlton 3053
JOIN ON ZOOM – MEETING ID: 873 1557 5255; PASSWORD: 778635

SEMINAR: WED  17 SEPTEMBER 2025 16:00-17:00 (AEST, Melbourne Time)