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

arXiv: https://arxiv.org/abs/2306.07608 · HTML: https://mlsanity.com/paper/2306.07608/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 48 references that are in the map.
- First posted on arXiv 13 Jun 2023.

## Builds on (most cited first, 30 of 36)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Federated Learning on Non-IID Graphs via Structural Knowledge Sharing](https://mlsanity.com/paper/2211.13009/) (2022)
- [Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs](https://mlsanity.com/paper/2202.08408/) (2022)
- [Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination](https://mlsanity.com/paper/2206.01535/) (2022)
- [Tackling Over-Smoothing for General Graph Convolutional Networks](https://mlsanity.com/paper/2008.09864/) (2020)
- [Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating](https://mlsanity.com/paper/2211.14065/) (2022)
- [GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection](https://mlsanity.com/paper/2211.04208/) (2022)
- [Pseudo-Riemannian Graph Convolutional Networks](https://mlsanity.com/paper/2106.03134/) (2021)
- [Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks](https://mlsanity.com/paper/2003.11702/) (2020)
- [Spiking Graph Convolutional Networks](https://mlsanity.com/paper/2205.02767/) (2022)
- [Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs](https://mlsanity.com/paper/2302.12357/) (2023)

## Built on by (most cited first, 25 of 25)

- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [ARC: A Generalist Graph Anomaly Detector with In-Context Learning](https://mlsanity.com/paper/2405.16771/) (2024)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Large Language Models-guided Dynamic Adaptation for Temporal Knowledge Graph Reasoning](https://mlsanity.com/paper/2405.14170/) (2024)
- [PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering](https://mlsanity.com/paper/2312.14438/) (2023)
- [PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection](https://mlsanity.com/paper/2310.11676/) (2023)
- [A Label-Free Heterophily-Guided Approach for Unsupervised Graph Fraud Detection](https://mlsanity.com/paper/2502.13308/) (2025)
- [GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels](https://mlsanity.com/paper/2310.14586/) (2023)
- [GOODAT: Towards Test-time Graph Out-of-Distribution Detection](https://mlsanity.com/paper/2401.06176/) (2024)
- [Self-Supervision Improves Diffusion Models for Tabular Data Imputation](https://mlsanity.com/paper/2407.18013/) (2024)
- [Feature Transportation Improves Graph Neural Networks](https://mlsanity.com/paper/2307.16092/) (2023)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation](https://mlsanity.com/paper/2405.14407/) (2024)
- [Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs](https://mlsanity.com/paper/2405.20652/) (2024)
- [Mixture of Weak & Strong Experts on Graphs](https://mlsanity.com/paper/2311.05185/) (2023)
- [Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily](https://mlsanity.com/paper/2511.06608/) (2025)
- [Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks](https://mlsanity.com/paper/2312.16418/) (2023)
- [RIDA: A Robust Attack Framework on Incomplete Graphs](https://mlsanity.com/paper/2407.18170/) (2024)
- [FedHERO: A Federated Learning Approach for Node Classification Task on Heterophilic Graphs](https://mlsanity.com/paper/2504.21206/) (2025)
- [Does Homophily Help in Robust Test-time Node Classification?](https://mlsanity.com/paper/2510.22289/) (2025)
- [A Generative Graph Contrastive Learning Model with Global Signal](https://mlsanity.com/paper/2504.18148/) (2025)
- [GraphTorque: Torque-Driven Rewiring Graph Neural Network](https://mlsanity.com/paper/2507.21422/) (2025)
- [Adaptive Graph Mixture of Residual Experts: Unsupervised Learning on Diverse Graphs with Heterogeneous Specialization](https://mlsanity.com/paper/2510.21207/) (2025)
- [Invariant-Stratified Propagation for Expressive Graph Neural Networks](https://mlsanity.com/paper/2603.01388/) (2026)
- [Continuous-Time Quantum Walks based Graph Neural Network](https://mlsanity.com/paper/2608.20738/) (2026)

## Abstract (arXiv)

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.