  Graph Neural Networks (GNNs) are emerging machine learning models on graphs.
Although sufficiently deep GNNs are shown theoretically capable of fully
preserving graph structures, most existing GNN models in practice are shallow
and essentially feature-centric. We show empirically and analytically that the
existing shallow GNNs cannot preserve graph structures well. To overcome this
fundamental challenge, we propose Eigen-GNN, a simple yet effective and general
plug-in module to boost GNNs ability in preserving graph structures.
Specifically, we integrate the eigenspace of graph structures with GNNs by
treating GNNs as a type of dimensionality reduction and expanding the initial
dimensionality reduction bases. Without needing to increase depths, Eigen-GNN
possesses more flexibilities in handling both feature-driven and
structure-driven tasks since the initial bases contain both node features and
graph structures. We present extensive experimental results to demonstrate the
effectiveness of Eigen-GNN for tasks including node classification, link
prediction, and graph isomorphism tests.
