CAREER: Demystifying and Mitigating Unfairness in Learning over Graphs

The science of networks has emerged as a major catalyst for understanding the behavior of complex interconnected entities, which can be described using graphs. For example, cyber-physical systems including the Internet of Things involve interactions among devices, and social networks can be modeled as graphs capturing various relationships among people or groups. Other complex networks emerge in diverse engineering fields, such as power grids and transportation systems. Graph-based machine learning (ML) and signal processing algorithms exhibit well-documented performance in learning over graphs (LoG). Despite their success, the impact of these algorithms in real-world systems depends heavily on how “socially responsible” they are. While graph-based ML models effectively integrate the nodal attributes with the topological information encoded by the graph, they also inherit and may even amplify potential unfairness. Using such models may subsequently result in unfair outcomes in decision- and policy-making in the related applications. While fairness issues have attracted increasing attention in general ML tasks, they are largely underexplored in the graph domain, especially in terms of theoretical analysis and fundamental understanding. To bridge this gap, the proposed research program will develop a systematic understanding of unfairness in LoG, leading to the design of efficient and principled algorithms for fair LoG. This project will further integrate an educational plan with the research goals, The proposed research will provide novel algorithmic as well as theoretical frameworks for fairness-aware Learning over graphs(LoG). The intellectual merit of this research entails transformative advances at the crossroads of machine learning, optimization, and network science to provide a principled means of mitigating potential bias in learning tasks over graphs. From a theoretical perspective, the proposed research provides new ways to systematically analyze the topological and attributive characteristics that result in unfairness, which are missing in existing studies. From an algorithmic perspective, the project offers principled designs of debiasing methods for mitigating unfairness in LoGs, which fill in the gap in existing works. These theoretical and algorithmic innovations have intrinsic intellectual value and create a “virtuous cycle.” The following research questions will be addressed: (RQ1) How to provide a theoretical understanding of the factors that lead to unfairness in LoG? (RQ2) How should one augment, compress, or generate fair graph data? (RQ3) How to design principled and fair LoG models? This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.