Enhancing link prediction in graph data augmentation through graphon mixup

Link prediction in complex networks is a fundamental problem with applications in diverse domains, from social networks to biological systems. Traditional approaches often struggle to capture intricate relationships in graphs, leading to suboptimal predictions. To address this, we introduce a novel method called graphon mixup (GM), which leverages the power of graphons to enhance link prediction. The augmentation strategy involves generating a synthetic graph by combining the original graph with a graphon-based synthetic graph. This process, expressed as a weighted combination of adjacency matrices, strategically blends real and synthetic information, enriching the training dataset. GM formulates link prediction as a joint optimization problem, aligning the characteristics of the synthetic graph with the true underlying structure. The objective is to minimize cross-entropy loss between predicted and true edge probabilities. A detailed computational complexity analysis evaluates the time and space requirements, aiding in understanding the efficiency and scalability of GM across different datasets and network sizes. Empirical validation on benchmark datasets demonstrates GM’s effectiveness in consistently improving average precision across diverse network types. The proposed method enhances the generalization capabilities of link prediction models, providing a more robust framework capable of accurate predictions even in the presence of noise or unseen patterns.