  Graph Neural Networks (GNNs) have shown great power in various domains.
However, their predictions may inherit societal biases on sensitive attributes,
limiting their adoption in real-world applications. Although many efforts have
been taken for fair GNNs, most existing works just adopt widely used fairness
techniques in machine learning to graph domains and ignore or don't have a
thorough understanding of the message passing mechanism with fairness
constraints, which is a distinctive feature of GNNs. To fill the gap, we
propose a novel fairness-aware message passing framework GMMD, which is derived
from an optimization problem that considers both graph smoothness and
representation fairness. GMMD can be intuitively interpreted as encouraging a
node to aggregate representations of other nodes from different sensitive
groups while subtracting representations of other nodes from the same sensitive
group, resulting in fair representations. We also provide a theoretical
analysis to justify that GMMD can guarantee fairness, which leads to a simpler
and theory-guided variant GMMD-S. Extensive experiments on graph benchmarks
show that our proposed framework can significantly improve the fairness of
various backbone GNN models while maintaining high accuracy.
