# Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns

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

## Key facts

- Cited by 95 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 54 references that are in the map.
- First posted on arXiv 11 Jun 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [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)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Learning to Represent Programs with Graphs](https://mlsanity.com/paper/1711.00740/) (2017)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification](https://mlsanity.com/paper/1906.02319/) (2019)

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

- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing](https://mlsanity.com/paper/2302.01524/) (2023)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond](https://mlsanity.com/paper/2209.06177/) (2022)
- [Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating](https://mlsanity.com/paper/2211.14065/) (2022)
- [Simplifying approach to Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2111.06748/) (2021)
- [GREAD: Graph Neural Reaction-Diffusion Networks](https://mlsanity.com/paper/2211.14208/) (2022)
- [Simple and Asymmetric Graph Contrastive Learning without Augmentations](https://mlsanity.com/paper/2310.18884/) (2023)
- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering](https://mlsanity.com/paper/2312.14438/) (2023)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs](https://mlsanity.com/paper/2302.12357/) (2023)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Improving Graph Neural Networks with Learnable Propagation Operators](https://mlsanity.com/paper/2210.17224/) (2022)
- [Permutation Equivariant Graph Framelets for Heterophilous Graph Learning](https://mlsanity.com/paper/2306.04265/) (2023)
- [Interpreting Unfairness in Graph Neural Networks via Training Node Attribution](https://mlsanity.com/paper/2211.14383/) (2022)
- [Simplified Graph Convolution with Heterophily](https://mlsanity.com/paper/2202.04139/) (2022)
- [Node-oriented Spectral Filtering for Graph Neural Networks](https://mlsanity.com/paper/2212.03654/) (2022)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (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)
- [Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity](https://mlsanity.com/paper/2308.09517/) (2023)
- [ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting](https://mlsanity.com/paper/2205.13700/) (2022)
- [MUSE: Multi-View Contrastive Learning for Heterophilic Graphs](https://mlsanity.com/paper/2307.16026/) (2023)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Decoupled Self-supervised Learning for Non-Homophilous Graphs](https://mlsanity.com/paper/2206.03601/) (2022)
- [SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation](https://mlsanity.com/paper/2305.09958/) (2023)

## Abstract (arXiv)

Graph neural networks (GNNs) have achieved tremendous success on multiple graph-based learning tasks by fusing network structure and node features. Modern GNN models are built upon iterative aggregation of neighbor's/proximity features by message passing. Its prediction performance has been shown to be strongly bounded by assortative mixing in the graph, a key property wherein nodes with similar attributes mix/connect with each other. We observe that real world networks exhibit heterogeneous or diverse mixing patterns and the conventional global measurement of assortativity, such as global assortativity coefficient, may not be a representative statistic in quantifying this mixing. We adopt a generalized concept, node-level assortativity, one that is based at the node level to better represent the diverse patterns and accurately quantify the learnability of GNNs. We find that the prediction performance of a wide range of GNN models is highly correlated with the node level assortativity. To break this limit, in this work, we focus on transforming the input graph into a computation graph which contains both proximity and structural information as distinct type of edges. The resulted multi-relational graph has an enhanced level of assortativity and, more importantly, preserves rich information from the original graph. We then propose to run GNNs on this computation graph and show that adaptively choosing between structure and proximity leads to improved performance under diverse mixing. Empirically, we show the benefits of adopting our transformation framework for semi-supervised node classification task on a variety of real world graph learning benchmarks.