Algorithmic Fairness in Graph Machine Learning: Explanation, Optimization, and Certification

Network data is ubiquitous across diverse domains such as credit scoring, social networking, recommendation systems, and medical diagnosis. In this landscape, graph machine learning algorithms, e.g., Graph Neural Networks (GNNs), have emerged as powerful tools for modeling such data and performing predictive tasks. However, despite the effectiveness of existing graph machine learning algorithms, they usually bear the problem of exhibiting bias in the prediction results. This is particularly alarming under high-stakes decision-making contexts, since these algorithms could play pivotal roles and influence life-altering choices for involved individuals. Consequently, it becomes paramount to delve into the root causes of such biases and improve the level of fairness, thereby enhancing the trustworthiness of these algorithms.

Nevertheless, addressing such a problem is non-trivial, and a plethora of unresolved questions loom large. For example, why does bias arise in graph machine learning? How to quantitatively measure the exhibited bias under different notions? How can we mitigate these biases, ensuring fair outcomes when these algorithms guide critical decisions? How to robustify the fairness level of graph machine learning algorithms against potential malicious attacks? How to remove the sensitive information that may lead to bias when it has been encoded in the graph machine learning algorithms in the training stage? It is necessary to properly answer these questions to ensure the trustworthiness of graph machine learning algorithms deployed in real-world applications. However, despite the significance of the algorithmic bias issue, the corresponding study remains at an early stage.

To answer the questions above, my Ph.D. dissertation mainly contributes to the advancement of graph machine learning through a fairness lens. Specifically, this dissertation mainly focuses on three research themes, including algorithmic fairness explanation in graph machine learning, algorithmic fairness optimization in graph machine learning, and fairness certification in graph machine learning. In the first theme, we present qualitative and quantitative analysis to understand why bias arises and where the bias comes from in graph machine learning. In the second theme, we present principled frameworks and strategies to mitigate the bias exhibited in graph machine learning algorithms, where multiple fairness notions are taken into consideration. In the third theme, we propose theoretical certification on graph machine learning algorithms to achieve defense on the level of fairness and removal of sensitive information that may bring bias from the model to achieve protection for privacy.

With these research themes, this dissertation aims to enhance the understanding of fair decision-making in the realm of graph machine learning and paves the way for future advances.