  The Lipschitz bound, a technique from robust statistics, can limit the
maximum changes in the output concerning the input, taking into account
associated irrelevant biased factors. It is an efficient and provable method
for examining the output stability of machine learning models without incurring
additional computation costs. Recently, Graph Neural Networks (GNNs), which
operate on non-Euclidean data, have gained significant attention. However, no
previous research has investigated the GNN Lipschitz bounds to shed light on
stabilizing model outputs, especially when working on non-Euclidean data with
inherent biases. Given the inherent biases in common graph data used for GNN
training, it poses a serious challenge to constraining the GNN output
perturbations induced by input biases, thereby safeguarding fairness during
training. Recently, despite the Lipschitz constant's use in controlling the
stability of Euclideanneural networks, the calculation of the precise Lipschitz
constant remains elusive for non-Euclidean neural networks like GNNs,
especially within fairness contexts. To narrow this gap, we begin with the
general GNNs operating on an attributed graph, and formulate a Lipschitz bound
to limit the changes in the output regarding biases associated with the input.
Additionally, we theoretically analyze how the Lipschitz constant of a GNN
model could constrain the output perturbations induced by biases learned from
data for fairness training. We experimentally validate the Lipschitz bound's
effectiveness in limiting biases of the model output. Finally, from a training
dynamics perspective, we demonstrate why the theoretical Lipschitz bound can
effectively guide the GNN training to better trade-off between accuracy and
fairness.
