  Fairness in graph neural networks has been actively studied recently.
However, existing works often do not explicitly consider the role of message
passing in introducing or amplifying the bias. In this paper, we first
investigate the problem of bias amplification in message passing. We
empirically and theoretically demonstrate that message passing could amplify
the bias when the 1-hop neighbors from different demographic groups are
unbalanced. Guided by such analyses, we propose BeMap, a fair message passing
method, that leverages a balance-aware sampling strategy to balance the number
of the 1-hop neighbors of each node among different demographic groups.
Extensive experiments on node classification demonstrate the efficacy of BeMap
in mitigating bias while maintaining classification accuracy. The code is
available at https://github.com/xiaolin-cs/BeMap.
