# Mitigating Degree Biases in Message Passing Mechanism by Utilizing Community Structures

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 28 Dec 2023.

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

- [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)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Deep Graph Contrastive Representation Learning](https://mlsanity.com/paper/2006.04131/) (2020)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Uncovering the Structural Fairness in Graph Contrastive Learning](https://mlsanity.com/paper/2210.03011/) (2022)
- [Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity](https://mlsanity.com/paper/2308.09517/) (2023)
- [Relational Self-Supervised Learning on Graphs](https://mlsanity.com/paper/2208.10493/) (2022)
- [Companion Animal Disease Diagnostics based on Literal-aware Medical Knowledge Graph Representation Learning](https://mlsanity.com/paper/2309.03219/) (2023)

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

- [GraphFM: A generalist graph transformer that learns transferable representations across diverse domains](https://mlsanity.com/paper/2407.11907/) (2024)
- [A Survey on Structure-Preserving Graph Transformers](https://mlsanity.com/paper/2401.16176/) (2024)
- [Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks](https://mlsanity.com/paper/2404.03139/) (2024)
- [Graph Neural Networks Need Cluster-Normalize-Activate Modules](https://mlsanity.com/paper/2412.04064/) (2024)
- [Refining Interactions: Enhancing Anisotropy in Graph Neural Networks with Language Semantics](https://mlsanity.com/paper/2504.01429/) (2025)
- [Fairness of Explanations in Artificial Intelligence (AI): A Unifying Framework, Axioms, and Future Direction toward Responsible AI](https://mlsanity.com/paper/2605.09852/) (2026)

## Abstract (arXiv)

This study utilizes community structures to address node degree biases in message-passing (MP) via learnable graph augmentations and novel graph transformers. Recent augmentation-based methods showed that MP neural networks often perform poorly on low-degree nodes, leading to degree biases due to a lack of messages reaching low-degree nodes. Despite their success, most methods use heuristic or uniform random augmentations, which are non-differentiable and may not always generate valuable edges for learning representations. In this paper, we propose Community-aware Graph Transformers, namely CGT, to learn degree-unbiased representations based on learnable augmentations and graph transformers by extracting within community structures. We first design a learnable graph augmentation to generate more within-community edges connecting low-degree nodes through edge perturbation. Second, we propose an improved self-attention to learn underlying proximity and the roles of nodes within the community. Third, we propose a self-supervised learning task that could learn the representations to preserve the global graph structure and regularize the graph augmentations. Extensive experiments on various benchmark datasets showed CGT outperforms state-of-the-art baselines and significantly improves the node degree biases. The source code is available at https://github.com/NSLab-CUK/Community-aware-Graph-Transformer.