Understanding the Effect of GCN Convolutions in Regression Tasks
This provides incremental theoretical insights for practitioners using GCNs in regression tasks, addressing a knowledge gap in their statistical properties.
The paper tackles the lack of statistical theory for Graph Convolutional Networks (GCNs) by analyzing how GCN and GraphSAGE convolutions affect learning error based on neighborhood topology and layers, characterizing a bias-variance trade-off and identifying less effective graph topologies, with synthetic experiments supporting the findings.
Graph Convolutional Networks (GCNs) have become a pivotal method in machine learning for modeling functions over graphs. Despite their widespread success across various applications, their statistical properties (e.g., consistency, convergence rates) remain ill-characterized. To begin addressing this knowledge gap, we consider networks for which the graph structure implies that neighboring nodes exhibit similar signals and provide statistical theory for the impact of convolution operators. Focusing on estimators based solely on neighborhood aggregation, we examine how two common convolutions - the original GCN and GraphSAGE convolutions - affect the learning error as a function of the neighborhood topology and the number of convolutional layers. We explicitly characterize the bias-variance type trade-off incurred by GCNs as a function of the neighborhood size and identify specific graph topologies where convolution operators are less effective. Our theoretical findings are corroborated by synthetic experiments, and provide a start to a deeper quantitative understanding of convolutional effects in GCNs for offering rigorous guidelines for practitioners.