Algorithmic foundation of fair graph mining

In an increasingly connected world, graph mining plays a fundamental role in many real-world applications, such as financial fraud detection, drug discovery, traffic prediction, and so on. Years of research in this area have developed a wealth of theories, algorithms, and systems that are successful in answering what/who types of questions, e.g., who is most influential in a social network? What item should we recommend to a user? Despite the remarkable progress in graph mining, unfairness often occurs in many graph mining tasks. As such, a fundamental question largely remains nascent: how can we make graph mining process and its results fair? To answer this question, it is crucial to propose a paradigm shift, from answering what and who to answering how and why. Four desired properties are called for to build an algorithmic foundation of fair graph mining, including: utility that promises strong empirical performance in the mining task, fairness that avoids discriminatory performances over diverse sensitive groups or individuals, robustness that enhances the resilience toward noise or adversarial activities in the complex world, and transparency that renders the accountability and explainability of graph mining algorithms. The tensions among the desired properties require us to address three key challenges, namely the auditing challenge, the debiasing challenge, and the safeguarding challenge. First, the auditing challenge requires to address the tension between utility and transparency by understanding how the mining results of a given graph mining model relate to the input graph. Second, the debiasing challenge asks for balancing the trade-off between utility and fairness so as to ensure fairness on graph mining without much sacrifice on its utility. Third, the safeguarding challenge connects utility, fairness, robustness, and transparency together, and studies the tensions among them, which could help the deployment of fair graph mining techniques in the real world. The theme of my Ph.D. research is to build an algorithmic foundation of fair graph mining by developing computational models underpinning all three pillars, namely auditing, debiasing, and safeguarding, to address these key challenges. First, for auditing, we develop a family of algorithms AURORA to audit PageRank algorithm from the edge, node, and subgraph level, and a generic algorithmic framework N2N that audits a variety of graph mining algorithms from the optimization perspective. Moreover, we develop JuryGCN, which is the first frequentist-based approach to quantify node uncertainty of graph convolutional network without any epoch(s) of model training. JuryGCN is proven to be useful in both active learning on node classification and semi-supervised node classification, and achieves the best effectiveness and lowest memory usage than the competitors. Second, for debiasing, we offer the first systematic study of individual fairness on graph mining (InFoRM), including the measurement, mitigation strategies, and cost. We also design a family of algorithms RawlsGCN to debias degree unfairness by analyzing its mathematical root cause. Moreover, we ensure fairness among intersectional groups from the information-theoretic perspective. Third, for safeguarding, we explore the adversarial robustness of fair graph mining algorithms by attacking them with a meta learning-based attacking framework named FATE. The developed framework is broadly applicable to various fairness definitions and graph learning models, as well as arbitrary choices of manipulation operations. We also conduct analysis on the poisoned edges to reveal edges with which property would contribute most to the bias amplification on graph neural networks.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Kang, Jian

Contributors dc:contributor

• Tong, Hanghang
• Han, Jiawei
• Maciejewski, Ross
• Zhao, Han

• Graph Mining
• Algorithmic Fairness
• Trustworthy Artificial Intelligence

Statement dc:rights

• Copyright 2023 Jian Kang

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121924

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121924