Mitigating Degree Biases in Message Passing Mechanism by Utilizing
  Community Structures
Van Thuy Hoang O-Joun Lee
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.