{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121924"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121924","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithmic foundation of fair graph mining","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","abstract_has_math":false,"creators":["Kang, Jian"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Tong, Hanghang","Han, Jiawei","Maciejewski, Ross","Zhao, Han"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-12","date_published":"2023-12","updated_at":"2026-07-22T22:25:00Z","subjects":["Graph Mining","Algorithmic Fairness","Trustworthy Artificial Intelligence"],"languages":["en","eng"],"rights":["Copyright 2023 Jian Kang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121924","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Tong, Hanghang","Han, Jiawei","Maciejewski, Ross","Zhao, Han"]},{"key":"dc:creator","label":"Author","values":["Kang, Jian"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-12","2023-07-31"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Mining","Algorithmic Fairness","Trustworthy Artificial Intelligence"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Jian Kang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121924"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","The student, Jian Kang, accepted the attached license on 2023-07-27 at 13:23.","The student, Jian Kang, submitted this Dissertation for approval on 2023-07-27 at 13:38.","This Dissertation was approved for publication on 2023-07-31 at 09:06.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19787 on 2024-03-01 at 13:13:05","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithmic foundation of fair graph mining"]}]}],"canonical_facts":{"dc:contributor":["Tong, Hanghang","Han, Jiawei","Maciejewski, Ross","Zhao, Han"],"dc:creator":["Kang, Jian"],"dc:date":["2023-12","2023-07-31"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","The student, Jian Kang, accepted the attached license on 2023-07-27 at 13:23.","The student, Jian Kang, submitted this Dissertation for approval on 2023-07-27 at 13:38.","This Dissertation was approved for publication on 2023-07-31 at 09:06.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19787 on 2024-03-01 at 13:13:05","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121924"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Jian Kang"],"dc:subject":["Graph Mining","Algorithmic Fairness","Trustworthy Artificial Intelligence"],"dc:title":["Algorithmic foundation of fair graph mining"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:00Z"}