Neural Tangent Kernels Motivate Graph Neural Networks with
  Cross-Covariance Graphs
Shervin Khalafi Saurabh Sihag Alejandro Ribeiro
Neural tangent kernels (NTKs) provide a theoretical regime to analyze the
learning and generalization behavior of over-parametrized neural networks. For
a supervised learning task, the association between the eigenvectors of the NTK
kernel and given data (a concept referred to as alignment in this paper) can
govern the rate of convergence of gradient descent, as well as generalization
to unseen data. Building upon this concept, we investigate NTKs and alignment
in the context of graph neural networks (GNNs), where our analysis reveals that
optimizing alignment translates to optimizing the graph representation or the
graph shift operator in a GNN. Our results further establish the theoretical
guarantees on the optimality of the alignment for a two-layer GNN and these
guarantees are characterized by the graph shift operator being a function of
the cross-covariance between the input and the output data. The theoretical
insights drawn from the analysis of NTKs are validated by our experiments
focused on a multi-variate time series prediction task for a publicly available
dataset. Specifically, they demonstrate that GNNs with cross-covariance as the
graph shift operator indeed outperform those that operate on the covariance
matrix from only the input data.