From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning

Real-world graph datasets often arise from mixtures of populations, where graphs are generated by multiple distinct underlying distributions. In this work, we propose a unified framework that explicitly models graph data as a mixture of probabilistic graph generative models represented by graphons. To characterize and estimate these graphons, we leverage graph moments (motif densities) to cluster graphs generated from the same underlying model. We establish a novel theoretical guarantee, deriving a tighter bound showing that graphs sampled from structurally similar graphons exhibit similar motif densities with high probability. This result enables principled estimation of graphon mixture components. We show how incorporating estimated graphon mixture components enhances two widely used downstream paradigms: graph data augmentation via mixup and graph contrastive learning. By conditioning these methods on the underlying generative models, we develop graphon-mixture-aware mixup (GMAM) and model-aware graph contrastive learning (MGCL). Extensive experiments on both simulated and real-world datasets demonstrate strong empirical performance. In supervised learning, GMAM outperforms existing augmentation strategies, achieving new state-of-the-art accuracy on 6 out of 7 datasets. In unsupervised learning, MGCL performs competitively across seven benchmark datasets and achieves the lowest average rank overall.

Many real-world networks such as molecules, social communities, and protein structures, come bundled together in datasets, and it's tempting to assume they were all built by the same underlying blueprint. But often they weren't: a single dataset can contain several distinct families of networks, each formed by a different process. Treating them all as one blurs these differences and weakens any model trained on them. We developed a method that automatically separates networks into groups based on their structural "fingerprints" - counts of small recurring patterns like triangles and chains. We proved mathematically that networks built by similar processes leave similar fingerprints, which lets us reliably separate the hidden families and learn a generative blueprint for each one. We then used these recovered blueprints to improve two widely used machine learning techniques for networks, leading to more accurate and trustworthy predictions. This helps researchers better capture the true diversity inside network datasets instead of forcing everything into a single mold.