  Learning fair graph representations for downstream applications is becoming
increasingly important, but existing work has mostly focused on improving
fairness at the global level by either modifying the graph structure or
objective function without taking into account the local neighborhood of a
node. In this work, we formally introduce the notion of neighborhood fairness
and develop a computational framework for learning such locally fair
embeddings. We argue that the notion of neighborhood fairness is more
appropriate since GNN-based models operate at the local neighborhood level of a
node. Our neighborhood fairness framework has two main components that are
flexible for learning fair graph representations from arbitrary data: the first
aims to construct fair neighborhoods for any arbitrary node in a graph and the
second enables adaption of these fair neighborhoods to better capture certain
application or data-dependent constraints, such as allowing neighborhoods to be
more biased towards certain attributes or neighbors in the graph.Furthermore,
while link prediction has been extensively studied, we are the first to
investigate the graph representation learning task of fair link classification.
We demonstrate the effectiveness of the proposed neighborhood fairness
framework for a variety of graph machine learning tasks including fair link
prediction, link classification, and learning fair graph embeddings. Notably,
our approach achieves not only better fairness but also increases the accuracy
in the majority of cases across a wide variety of graphs, problem settings, and
metrics.
