The Graphical Nadaraya-Watson Estimator on Latent Position Models
This work addresses theoretical understanding of graph learning methods, which is incremental for researchers in graph machine learning.
The paper analyzes the theoretical properties of a simple averaging estimator that predicts node labels in graphs by averaging labeled neighbors' observations, providing rigorous concentration properties, variance bounds, and risk bounds.
Given a graph with a subset of labeled nodes, we are interested in the quality of the averaging estimator which for an unlabeled node predicts the average of the observations of its labeled neighbors. We rigorously study concentration properties, variance bounds and risk bounds in this context. While the estimator itself is very simple we believe that our results will contribute towards the theoretical understanding of learning on graphs through more sophisticated methods such as Graph Neural Networks.