  Graph Neural Networks (GNNs) have proven to excel in predictive modeling
tasks where the underlying data is a graph. However, as GNNs are extensively
used in human-centered applications, the issue of fairness has arisen. While
edge deletion is a common method used to promote fairness in GNNs, it fails to
consider when data is inherently missing fair connections. In this work we
consider the unexplored method of edge addition, accompanied by deletion, to
promote fairness. We propose two model-agnostic algorithms to perform edge
editing: a brute force approach and a continuous approximation approach,
FairEdit. FairEdit performs efficient edge editing by leveraging gradient
information of a fairness loss to find edges that improve fairness. We find
that FairEdit outperforms standard training for many data sets and GNN methods,
while performing comparably to many state-of-the-art methods, demonstrating
FairEdit's ability to improve fairness across many domains and models.
