  Graphs are mathematical tools that can be used to represent complex
real-world interconnected systems, such as financial markets and social
networks. Hence, machine learning (ML) over graphs has attracted significant
attention recently. However, it has been demonstrated that ML over graphs
amplifies the already existing bias towards certain under-represented groups in
various decision-making problems due to the information aggregation over biased
graph structures. Faced with this challenge, here we take a fresh look at the
problem of bias mitigation in graph-based learning by borrowing insights from
graph signal processing. Our idea is to introduce predesigned graph filters
within an ML pipeline to reduce a novel unsupervised bias measure, namely the
correlation between sensitive attributes and the underlying graph connectivity.
We show that the optimal design of said filters can be cast as a convex problem
in the graph spectral domain. We also formulate a linear programming (LP)
problem informed by a theoretical bias analysis, which attains a closed-form
solution and leads to a more efficient fairness-aware graph filter. Finally,
for a design whose degrees of freedom are independent of the input graph size,
we minimize the bias metric over the family of polynomial graph convolutional
filters. Our optimal filter designs offer complementary strengths to explore
favorable fairness-utility-complexity tradeoffs. For performance evaluation, we
conduct extensive and reproducible node classification experiments over
real-world networks. Our results show that the proposed framework leads to
better fairness measures together with similar utility compared to
state-of-the-art fairness-aware baselines.
