CAREER: Bilevel Optimization for Accountable Machine Learning on Graphs

该奖项全部或部分由《2021年美国救援计划法案》（公法117-2）资助。图形表示现实世界的实体及其联系，可以在不同的学科中找到，例如计算机科学、土木工程和生物信息学。机器学习是一项有用的技术，它可以在大规模图形数据集上做出决策，以帮助防止网络攻击，减少能源浪费，发明新的疾病治疗方法。不幸的是，复杂的图结构降低了机器决策的责任，这可能是1)人类用户难以理解的，2)对某些子群体或个体的歧视。该项目将结合人类对图形的先验知识，作为机器决策的透明度和公平性约束。在不同的需求下，该项目将全面发现多个竞争性透明度和公平目标的有用权衡，以帮助人类理解和采用机器决策。由于图的变化，机器决策的波动性可能会危及它们的问责制，并且项目将发现变化的条件，在这些条件下，可以并且应该期望强大的透明度和公平性。政府、监管机构和组织可以依靠发明的技术来审计民用基础设施运营、在线社交网络和商业。从事材料、药物和人类大脑网络研究的科学家将从他们设计的约束中受益。通过出版物、教程、课程和研讨会，该项目将培训本科生和研究生，其中许多人的代表性不足。通过拓展活动，K6-12年级的学生将通过互动角色扮演电脑游戏和专为外行用户设计的讲座，学习图表上的机器学习。为了实现这些目标，该项目确定了问责机器学习中的新挑战，并在BLO（双层优化）框架下解决了这些挑战。与没有特定领域约束的问责制不同，该项目将设计人在循环约束生成方法，以帮助指定图形数据的相关约束。约束条件可能众多且不确定，因此，该项目发明了通过优化实现差异化、分层最接近方法和机会约束优化。与可问责机器学习的标量优化不同，该项目旨在有效的多目标权衡，并提出在BLO框架下的约束向量优化和局部Pareto前沿的持续探索。该项目将研究稳定的学习到先决条件，以利用BLO更新的平滑性来加速优化。为了量化决策问责制的鲁棒性，该框架搜索了通常未定义的可问责模型的鲁棒性和敏感性之间的边界。该项目提出了一种具有互补强化学习策略的信任区域搜索，以外科手术和差异平衡鲁棒性和敏感性。BLO框架为最优解释和公平模型提供了来源和元解释。该项目还将通过图划分、一阶近似和高级线性代数技术来解决BLO在大型图上的计算效率问题。最后，本课题将分析BLO问题的收敛性、唯一性和权衡性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.