Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs
This addresses a limitation in GNNs for graph learning tasks, offering a method to improve performance on both homophily-prone and heterophily-prone graphs, though it appears incremental by building on existing GNN frameworks.
The paper tackles the problem of graph neural networks (GNNs) ignoring complementary structural information (e.g., heterophily-prone topology for homophily-prone graphs) by introducing GOAL, which uses graph complementation and a new convolution method, resulting in consistent outperformance over baselines across eight real-world datasets.
Real-world graphs generally have only one kind of tendency in their connections. These connections are either homophily-prone or heterophily-prone. While graphs with homophily-prone edges tend to connect nodes with the same class (i.e., intra-class nodes), heterophily-prone edges tend to build relationships between nodes with different classes (i.e., inter-class nodes). Existing GNNs only take the original graph during training. The problem with this approach is that it forgets to take into consideration the ``missing-half" structural information, that is, heterophily-prone topology for homophily-prone graphs and homophily-prone topology for heterophily-prone graphs. In our paper, we introduce Graph cOmplementAry Learning, namely GOAL, which consists of two components: graph complementation and complemented graph convolution. The first component finds the missing-half structural information for a given graph to complement it. The complemented graph has two sets of graphs including both homophily- and heterophily-prone topology. In the latter component, to handle complemented graphs, we design a new graph convolution from the perspective of optimisation. The experiment results show that GOAL consistently outperforms all baselines in eight real-world datasets.