Connecting Graph Convolutional Networks and Graph-Regularized PCA
This work provides a theoretical insight into GCN's effectiveness, suggesting it is driven by graph regularization, and offers a general-purpose initialization strategy for faster convergence in GNNs.
The paper establishes a mathematical connection between Graph Convolutional Networks (GCN) and graph-regularized PCA (GPCA), showing that unsupervised GPCA embeddings with a simple MLP achieve similar or better performance than GCN on semi-supervised node classification across five datasets, including Open Graph Benchmark.
Graph convolution operator of the GCN model is originally motivated from a localized first-order approximation of spectral graph convolutions. This work stands on a different view; establishing a \textit{mathematical connection between graph convolution and graph-regularized PCA} (GPCA). Based on this connection, GCN architecture, shaped by stacking graph convolution layers, shares a close relationship with stacking GPCA. We empirically demonstrate that the \textit{unsupervised} embeddings by GPCA paired with a 1- or 2-layer MLP achieves similar or even better performance than GCN on semi-supervised node classification tasks across five datasets including Open Graph Benchmark \footnote{\url{https://ogb.stanford.edu/}}. This suggests that the prowess of GCN is driven by graph based regularization. In addition, we extend GPCA to the (semi-)supervised setting and show that it is equivalent to GPCA on a graph extended with "ghost" edges between nodes of the same label. Finally, we capitalize on the discovered relationship to design an effective initialization strategy based on stacking GPCA, enabling GCN to converge faster and achieve robust performance at large number of layers. Notably, the proposed initialization is general-purpose and applies to other GNNs.