Connecting Graph Convolutional Networks and Graph-Regularized PCA
arXiv:2006.12294
Abstract
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.
arXiv commentUnder review
References in corpus (15)
- Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
- Inductive Representation Learning on Large Graphs
- Fast Graph Representation Learning with PyTorch Geometric
- Simplifying Graph Convolutional Networks
- Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
- PairNorm: Tackling Oversmoothing in GNNs
- All you need is a good init
- Data-dependent Initializations of Convolutional Neural Networks
- A Fair Comparison of Graph Neural Networks for Graph Classification
- Fast Robust PCA on Graphs
- Can Graph Neural Networks Count Substructures?
- On the Equivalence between Positional Node Embeddings and Structural Graph Representations
- How hard is to distinguish graphs with graph neural networks?