Papers › Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach
Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach
Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, Dongmei Zhang
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.
In Syntology View this paper on Syntology: its repositories, every harvested function with whether it ran, its licence and the call to fetch it.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
No code repository is listed for this paper in the archive or in Syntology's graph.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
| Task | Dataset | Model | Metric | Value | Rank at snapshot | Leaderboard | Report |
|---|---|---|---|---|---|---|---|
| Node Classification | Actor | GPRGNN+DHGR | Accuracy | 37.43 ± 0.78 | #24 of 62 | Archive leaderboard | report |
| Node Classification | Chameleon | GCNII+DHGR | Accuracy | 74.57±2.56 | #13 of 61 | Archive leaderboard | report |
| Node Classification | Cornell | GraphSAGE+DHGR | Accuracy | 82.88±5.56 | #33 of 60 | Archive leaderboard | report |
| Node Classification | Squirrel | H2GCN+DHGR | Accuracy | 72.24±1.52 | #7 of 59 | Archive leaderboard | report |
| Node Classification | Texas | H2GCN+DHGR | Accuracy | 84.86±5.01 | #32 of 62 | Archive leaderboard | report |
| Node Classification | Wisconsin | H2GCN DHGR | Accuracy | 85.01±5.51 | #44 of 63 | Archive leaderboard | report |
Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections