This thesis concerns the nonparametric estimation of decorated graphons, symmetric measurable functions W:[0,1]2→P(K) that generalize classical graphon models beyond binary edges to networks carrying rich edge attributes such as weights and types. While decorated graphons were introduced as limit objects in graph theory, no estimation theory was available prior to this work. The thesis addresses this gap along three axes: rich edge attributes, temporal dynamics, and computational scalability.
In the introduction, we provide an overview of the decorated graphon framework and its statistical foundations, and describe how the contributions of each chapter relate to one another.
Chapter 1 develops the first consistent estimator for decorated graphons with finite or compact decoration spaces. We extend the Stochastic Shape Model to distribution-valued edge parameters, establish convergence rates that make explicit the cost of estimating the full edge distribution rather than a scalar summary, and show that this cost scales linearly in the number of decoration levels while preserving the classical dependence on the number of nodes. The method is validated on simulated data and on a disease comorbidity multiplex network.
Chapter 2 shows that dynamic networks can be absorbed into the decorated graphon framework by encoding each edge's temporal evolution as a decoration. We propose a modular two-stage estimator that decouples temporal modeling from network clustering and prove convergence rates in which the estimation error decomposes into a spatial term, governed by the graphon's smoothness, and a temporal term, governed by the quality of edge-level estimation. We derive explicit rates for Bernoulli and Markov chain edge processes.
Chapter 3 addresses the NP-hard combinatorial node assignment problem that is common to all graphon estimation methods. We cast the problem as a semi-relaxed Gromov-Wasserstein barycenter problem, replacing deterministic assignments with probabilistic couplings. We prove that optimal couplings concentrate near deterministic assignments, with a relaxation gap that vanishes at a controlled rate, and leverage this to establish minimax-optimal convergence rates for both stochastic block models and Hölder-smooth graphons. A GPU-compatible conditional gradient algorithm solves the resulting optimization efficiently at scale.
Chapter 4 discusses open problems and extensions, and proposes GraphonXAI, a research direction using the generative capacity of decorated graphons to construct data-driven benchmarks for graph neural network explainability. With the exception of Chapter 4, all chapters are based on self-contained research articles and can be read independently, although the given order is recommended.
