Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs

Abstract

Real-world graphs generally have only one kind of tendency in their connections. These connections are either homophilic-prone or heterophilic-prone. While graphs with homophilic-prone edges tend to connect nodes with the same class (i.e., intra-class nodes), heterophilic-prone edges tend to build relationships between nodes with different classes (i.e., inter-class nodes). Existing GNNs only take the original graph as input during training. The problem with this approach is that it forgets to take into consideration the ‘‘missing-half’’ structural information, that is, heterophilic-prone topology for homophilic-prone graphs and homophilic-prone topology for heterophilic-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 homophilic- and heterophilic-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.