CAREER: Bilevel Optimization for Accountable Machine Learning on Graphs

Lehigh University, Bethlehem PA

Investigators

Abstract

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). Graphs represent real-world entities and their connections, found in diverse disciplines, such as computer science, civil engineering, and bioinformatics. Machine learning is a useful technique that can make decisions on large-scale graph datasets to help prevent cyberattacks, reduce energy waste, invent new cures for diseases. Unfortunately, complicated graph structures reduce the accountability of machine decisions, which can be 1) hard for human users to comprehend, and 2) discriminative against certain subpopulations or individuals. The project will incorporate prior human knowledge about graphs as transparency and fairness constraints over machine decisions. With diverse desiderata, the project will comprehensively discover useful trade-offs of multiple competitive transparency and fairness objectives to help humans make sense of and adopt machine decisions. Due to graph variations, volatility in machine decisions can jeopardize their accountability, and the project will discover the conditions of variations under which robust transparency and fairness can and should be expected. Governments, regulators, and organizations can rely on the invented techniques to audit civil infrastructure operations, online social networks, and commerce. Scientists working on materials, drugs, and human brain networks will benefit from the accountability through the constraints designed by them. Via publications, tutorials, courses, and workshops, the project will train undergraduates and graduates, many of whom are underrepresented. K6-12 students will be educated about machine learning on graphs, using an interactive role-playing computer game, and lectures designed for the lay users, through outreach activities. To meet these goals, this project identifies new challenges in accountable ML and addresses them under the BLO (bilevel optimization) framework. Unlike accountability without domain-specific constraints, the project will design human-in-the-loop constraint generation methods to help specify relevant constraints for graph data. Constraints can be numerous and uncertain, and accordingly, the project invents differentiation-through-optimization, hierarchical proximal methods, and chance-constrained optimization. Unlike scalar optimization of accountable ML, the project aims at efficient multi-objective trade-offs and proposes constrained vector optimization and continuous exploration of local Pareto fronts under the BLO framework. The project will investigate stable learning-to-precondition to exploit the smoothness of the BLO updates to speed up the optimization. To quantify the robustness of the decision accountability, the framework searches the usually undefined boundary between robustness and sensitivity of accountable models. The project proposes a trust-region search with complementary reinforcement learning policies to surgically and differentially balance robustness and sensitivity. The BLO framework provides provenance and meta-explanations for the optimal explanations and fair models. The project will also address the computational efficiency of BLO on large graphs through graph partition, first-order approximation, and advanced linear algebra techniques. Lastly, the project will analyze the convergence, uniqueness, and trade-offs in the BLO problems. 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.