  Graph embedding techniques are pivotal in real-world machine learning tasks
that operate on graph-structured data, such as social recommendation and
protein structure modeling. Embeddings are mostly performed on the node level
for learning representations of each node. Since the formation of a graph is
inevitably affected by certain sensitive node attributes, the node embeddings
can inherit such sensitive information and introduce undesirable biases in
downstream tasks. Most existing works impose ad-hoc constraints on the node
embeddings to restrict their distributions for unbiasedness/fairness, which
however compromise the utility of the resulting embeddings. In this paper, we
propose a principled new way for unbiased graph embedding by learning node
embeddings from an underlying bias-free graph, which is not influenced by
sensitive node attributes. Motivated by this new perspective, we propose two
complementary methods for uncovering such an underlying graph, with the goal of
introducing minimum impact on the utility of the embeddings. Both our
theoretical justification and extensive experimental comparisons against
state-of-the-art solutions demonstrate the effectiveness of our proposed
methods.
