# Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

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

## Key facts

- Cited by 179 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 35 references that are in the map.
- First posted on arXiv 15 May 2022.

## Builds on (most cited first, 27 of 27)

- [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)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [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)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Graph Neural Networks Inspired by Classical Iterative Algorithms](https://mlsanity.com/paper/2103.06064/) (2021)
- [Robust and Efficient Subspace Segmentation via Least Squares Regression](https://mlsanity.com/paper/1404.6736/) (2014)
- [AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter](https://mlsanity.com/paper/2104.12840/) (2021)
- [Homophily and missing links in citation networks](https://mlsanity.com/paper/1511.07643/) (2015)
- [CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data](https://mlsanity.com/paper/2006.04435/) (2020)

## Built on by (most cited first, 30 of 179)

- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [GREAD: Graph Neural Reaction-Diffusion Networks](https://mlsanity.com/paper/2211.14208/) (2022)
- [Gradient Gating for Deep Multi-Rate Learning on Graphs](https://mlsanity.com/paper/2210.00513/) (2022)
- [A Fractional Graph Laplacian Approach to Oversmoothing](https://mlsanity.com/paper/2305.13084/) (2023)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering](https://mlsanity.com/paper/2312.14438/) (2023)
- [Graph Neural Convection-Diffusion with Heterophily](https://mlsanity.com/paper/2305.16780/) (2023)
- [AdaFGL: A New Paradigm for Federated Node Classification with Topology Heterogeneity](https://mlsanity.com/paper/2401.11750/) (2024)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [HoloNets: Spectral Convolutions do extend to Directed Graphs](https://mlsanity.com/paper/2310.02232/) (2023)
- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification](https://mlsanity.com/paper/2312.04111/) (2023)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FROND](https://mlsanity.com/paper/2404.17099/) (2024)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (2024)
- [LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity](https://mlsanity.com/paper/2305.04225/) (2023)
- [Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes](https://mlsanity.com/paper/2309.12971/) (2023)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graph](https://mlsanity.com/paper/2211.10890/) (2022)
- [ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting](https://mlsanity.com/paper/2205.13700/) (2022)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [MUSE: Multi-View Contrastive Learning for Heterophilic Graphs](https://mlsanity.com/paper/2307.16026/) (2023)
- [Even Sparser Graph Transformers](https://mlsanity.com/paper/2411.16278/) (2024)

## Abstract (arXiv)

We investigate graph neural networks on graphs with heterophily. Some existing methods amplify a node's neighborhood with multi-hop neighbors to include more nodes with homophily. However, it is a significant challenge to set personalized neighborhood sizes for different nodes. Further, for other homophilous nodes excluded in the neighborhood, they are ignored for information aggregation. To address these problems, we propose two models GloGNN and GloGNN++, which generate a node's embedding by aggregating information from global nodes in the graph. In each layer, both models learn a coefficient matrix to capture the correlations between nodes, based on which neighborhood aggregation is performed. The coefficient matrix allows signed values and is derived from an optimization problem that has a closed-form solution. We further accelerate neighborhood aggregation and derive a linear time complexity. We theoretically explain the models' effectiveness by proving that both the coefficient matrix and the generated node embedding matrix have the desired grouping effect. We conduct extensive experiments to compare our models against 11 other competitors on 15 benchmark datasets in a wide range of domains, scales and graph heterophilies. Experimental results show that our methods achieve superior performance and are also very efficient.