Theoretical Analyses of Hyperparameter Selection in Graph-Based Semi-Supervised Learning

Graph-based semi-supervised learning (SSL) is a powerful paradigm in machine learning for modeling and exploiting the underlying graph structure that captures the relationship between labeled and unlabeled data. A large number of classical as well as modern deep learning based algorithms have been proposed for this problem, often having tunable hyperparameters. Different values of hyperparameters define different node feature embedding in the underlying geometry and lead to different performances in terms of classification error.We initiate a formal study of hyperparameter tuning from parameterized algorithm families for this problem. We obtain novel $\Theta(\log n)$ pseudo-dimension upper bounds for hyperparameter selection in one of the classical label propagation based algorithm families, where $n$ is the number of nodes, implying bounds on the amount of data needed for learning provably good parameters.We extend our study to hyperparameter selection in modern graph neural networks. We propose a novel tunable architecture that interpolates graph convolutional neural networks (GCN) and graph attention networks (GAT) in every layer, which we call GCAN. We then provide Rademacher complexity bounds for tuning the interpolation coefficient and study the influence of the interpolation coefficient on the node feature in the latent space. Finally, we empirically verify the effectiveness of GCAN on benchmark datasets.