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.

Yizhen Zheng

PhD Student @ Monash (07/2021-)

My research interests include machine learning and artificial intelligence.

He Zhang

PhD

My research interests include data mining, machine learning, and graph analysis.

Shirui Pan

Professor and ARC Future Fellow

My research interests include data mining, machine learning, and graph analysis.