Model-free consistency of graph partitioning

Understand

In this paper, we exploit the theory of dense graph limits to provide a new framework to study the stability of graph partitioning methods, which we call structural consistency.

• Both stability under perturbation as well as asymptotic consistency (i.e., convergence with probability $1$ as the sample size goes to infinity under a fixed probability model) follow from our notion of structural consistency.
• By formulating structural consistency as a continuity result on the graphon space, we obtain robust results that are completely independent of the data generating mechanism.
• In particular, our results apply in settings where observations are not independent, thereby significantly generalizing the common probabilistic approach where data are assumed to be i.i.d.