  Graph Neural Networks (GNNs) are popular machine learning methods for
modeling graph data. A lot of GNNs perform well on homophily graphs while
having unsatisfactory performance on heterophily graphs. Recently, some
researchers turn their attention to designing GNNs for heterophily graphs by
adjusting the message passing mechanism or enlarging the receptive field of the
message passing. Different from existing works that mitigate the issues of
heterophily from model design perspective, we propose to study heterophily
graphs from an orthogonal perspective by rewiring the graph structure to reduce
heterophily and making the traditional GNNs perform better. Through
comprehensive empirical studies and analysis, we verify the potential of the
rewiring methods. To fully exploit its potential, we propose a method named
Deep Heterophily Graph Rewiring (DHGR) to rewire graphs by adding homophilic
edges and pruning heterophilic edges. The detailed way of rewiring is
determined by comparing the similarity of label/feature-distribution of node
neighbors. Besides, we design a scalable implementation for DHGR to guarantee
high efficiency. DHRG can be easily used as a plug-in module, i.e., a graph
pre-processing step, for any GNNs, including both GNN for homophily and
heterophily, to boost their performance on the node classification task. To the
best of our knowledge, it is the first work studying graph rewiring for
heterophily graphs. Extensive experiments on 11 public graph datasets
demonstrate the superiority of our proposed methods.
