  While a growing body of literature has been studying new Graph Neural
Networks (GNNs) that work on both homophilic and heterophilic graphs, little
has been done on adapting classical GNNs to less-homophilic graphs. Although
the ability to handle less-homophilic graphs is restricted, classical GNNs
still stand out in several nice properties such as efficiency, simplicity, and
explainability. In this work, we propose a novel graph restructuring method
that can be integrated into any type of GNNs, including classical GNNs, to
leverage the benefits of existing GNNs while alleviating their limitations. Our
contribution is threefold: a) learning the weight of pseudo-eigenvectors for an
adaptive spectral clustering that aligns well with known node labels, b)
proposing a new density-aware homophilic metric that is robust to label
imbalance, and c) reconstructing the adjacency matrix based on the result of
adaptive spectral clustering to maximize the homophilic scores. The
experimental results show that our graph restructuring method can significantly
boost the performance of six classical GNNs by an average of 25% on
less-homophilic graphs. The boosted performance is comparable to
state-of-the-art methods.
