CAREER: Bilevel Optimization for Accountable Machine Learning on Graphs

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

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.