Make Heterophilic Graphs Better Fit GNN: A Graph Rewiring Approach

Graph Neural Networks (GNNs) have shown superior performance in modeling graph data. Existing studies have shown that a lot of GNNs perform well on homophilic graphs while performing poorly on heterophilic graphs. Recently, researchers have turned their attention to design GNNs for heterophilic graphs by specific model design. Different from existing methods that mitigate heterophily by model design, we propose to study heterophilic graphs from an orthogonal perspective by rewiring the graph to reduce heterophily and make GNNs perform better. Through comprehensive empirical analysis, we verify the potential of graph rewiring methods. Then we propose a method named <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</b> eep <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</b> eterophily <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</b> raph <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</b> ewiring (DHGR) to rewire graphs by adding homophilic edges and pruning heterophilic edges. The rewiring operation is implemented by comparing the similarity of neighborhood label/feature distribution of node pairs. Besides, we design a scalable implementation for DHGR to guarantee a high efficiency. DHRG can be easily used as a plug-in module, i.e., a graph pre-processing step, for any GNNs, including both GNNs 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 heterophilic graphs. Extensive experiments on 11 public graph datasets demonstrate the superiority of our proposed methods.