SMRI Seminar: Kandanaarachchi -- Graphon challenges: The limit can exist, but not everything is sorted!

SMRI Seminar 

Date: 8th October 2026, 1.00pm - 2.00pm 

Location: SMRI Seminar Room (Macleay Building, Rm 301) 

Speaker: Sevvandi Kandanaarachchi, CSIRO 

Title: Graphon challenges: The limit can exist, but not everything is sorted! 

Abstract: Many real-world networks, including social media and telephone networks, grow
as new nodes and edges are added over time, making a limit object useful for describing
their large-scale structure independently of network size.  Graphons provide a way to
represent this infinite limit object.  Intuitively, a graphon can be obtained by scaling
the adjacency matrix to the unit square and taking its limit.  Traditionally, a graphon
is defined as a symmetric, measurable function on the unit square with function values
encoding edge probabilities.  Graphons serve both as graph limits and generative models
and can be used to sample graphs of arbitrary size.  

However, graphons are not without challenges.  The first and foremost concerns graph
generation: as a consequence of the Aldous–Hoover theorem, graphs generated by
traditional graphons are dense, limiting their utility to model sparse graphs.  This is
a serious limitation given that many real-world graphs such as social, biological and
infrastructure networks are sparse.  The second concerns graphon estimation: most
estimation methods require the nodes in each graph to be labelled consistently with the
underlying graphon.  Because this correspondence is typically unknown, many estimation
methods impose assumptions that enable it to be inferred from the observed graphs.  In
this talk, we will examine these two challenges and discuss some recent advances.