  Graph Convolutional Network (GCN) plays pivotal roles in many real-world
applications. Despite the successes of GCN deployment, GCN often exhibits
performance disparity with respect to node degrees, resulting in worse
predictive accuracy for low-degree nodes. We formulate the problem of
mitigating the degree-related performance disparity in GCN from the perspective
of the Rawlsian difference principle, which is originated from the theory of
distributive justice. Mathematically, we aim to balance the utility between
low-degree nodes and high-degree nodes while minimizing the task-specific loss.
Specifically, we reveal the root cause of this degree-related unfairness by
analyzing the gradients of weight matrices in GCN. Guided by the gradients of
weight matrices, we further propose a pre-processing method RawlsGCN-Graph and
an in-processing method RawlsGCN-Grad that achieves fair predictive accuracy in
low-degree nodes without modification on the GCN architecture or introduction
of additional parameters. Extensive experiments on real-world graphs
demonstrate the effectiveness of our proposed RawlsGCN methods in significantly
reducing degree-related bias while retaining comparable overall performance.
