  As the representations output by Graph Neural Networks (GNNs) are
increasingly employed in real-world applications, it becomes important to
ensure that these representations are fair and stable. In this work, we
establish a key connection between counterfactual fairness and stability and
leverage it to propose a novel framework, NIFTY (uNIfying Fairness and
stabiliTY), which can be used with any GNN to learn fair and stable
representations. We introduce a novel objective function that simultaneously
accounts for fairness and stability and develop a layer-wise weight
normalization using the Lipschitz constant to enhance neural message passing in
GNNs. In doing so, we enforce fairness and stability both in the objective
function as well as in the GNN architecture. Further, we show theoretically
that our layer-wise weight normalization promotes counterfactual fairness and
stability in the resulting representations. We introduce three new graph
datasets comprising of high-stakes decisions in criminal justice and financial
lending domains. Extensive experimentation with the above datasets demonstrates
the efficacy of our framework.
