Collaborative Research: Towards a Theoretic Foundation for Optimal Deep Graph Learning

协作研究：为最优深度图学习奠定理论基础

• 批准号: 2134080
• 负责人: Yuejie Chi
• 金额: $ 35万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-01-01 至 2024-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2134080&HistoricalAwards=false
• 关键词: Collaborative; Research; Towards; Theoretic; Foundation

Graph learning has become the cornerstone in numerous real-world applications, such as social media mining, brain connectivity analysis, computational epidemiology and financial fraud detection. Graph neural networks (GNNs for short) represent an important and emerging family of deep graph learning models. By producing a vector representation of graph elements, GNNs have largely streamlined a multitude of graph learning problems. In the vast majority of the existing works, they require a given graph, including its topology, the associated attribute information and labels for (semi-)supervised learning tasks, as part of the input of the corresponding learning model. Despite tremendous progress being made, a theoretical foundation of optimal deep graph learning is still missing, a gap that this project aims to fulfill. The outcomes of this project have broader impacts on education and society. The results of this project enrich the curriculum as well as summer outreach programs at participating institutions, and are further disseminated to the community through a variety of formats to create synergies and advance understandings of different disciplines. This project benefits a variety of high-impact graph learning based applications, including recommendation, power grid, neural science, team science and management, and intelligent transportation systems.This project examines the fundamental role of the input data, including graph topology, attributes and optional labels, in graph neural networks. There are three research thrusts in this project. The first thrust seeks to understand how sensitive the GNNs model is with respect to the input graph; how to quantify the uncertainty of the GNNs model; and how that impacts the generalization performance of the GNNs model. The second thrust develops algorithms to optimize the initially provided graph so as to maximally boost the generalization performance of the given GNNs model. The third thrust develops active learning methods based on deep reinforcement learning with entropy regularization to optimally obtain the additional labels to further improve the GNNs model. This project investigates new theoretic foundations in terms of the sensitivity, the uncertainty and the generalization performance of graph neural networks. It develops new algorithms for learning optimal graphs and active GNNs with better efficacy whose fundamental limits, including sample complexity, generalization error bound, optimality and convergence rate, are well understood.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.

图学习已经成为许多现实世界应用的基石，如社交媒体挖掘、大脑连通性分析、计算流行病学和金融欺诈检测。图神经网络是一类重要的、新兴的深度图学习模型。通过产生图形元素的矢量表示，GNN在很大程度上简化了大量的图形学习问题。在现有的绝大多数工作中，它们需要一个给定的图，包括它的拓扑结构、关联的属性信息和(半)监督学习任务的标签，作为相应学习模型的输入。尽管已经取得了巨大的进展，但最优深度图学习的理论基础仍然缺乏，这是本项目旨在填补的一个空白。该项目的成果对教育和社会产生了更广泛的影响。这一项目的成果丰富了参与机构的课程和暑期外展计划，并通过各种形式进一步向社区传播，以创造协同效应，增进对不同学科的了解。该项目有利于各种基于图学习的高影响应用，包括推荐、电网、神经科学、团队科学和管理以及智能交通系统。该项目研究了输入数据在图神经网络中的基本作用，包括图的拓扑、属性和可选标签。这个项目有三个研究重点。第一个重点是要了解全球导航网络模型对输入图表的敏感性；如何量化全球导航网络模型的不确定性；以及这如何影响全球导航网络模型的推广性能。第二个推力是开发算法来优化初始提供的图，以最大限度地提高给定GNN模型的泛化性能。第三个推力是提出了基于深度强化学习的主动学习方法，利用熵正则化来优化获取附加标签，以进一步改进GNNS模型。本项目从图神经网络的敏感度、不确定性和泛化性能三个方面探索了新的理论基础。它开发了学习最优图和主动GNN的新算法，具有更好的有效性，其基本限制，包括样本复杂性、泛化误差界、最佳性和收敛速度都得到了很好的理解。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence

• DOI: 10.1137/21m1456789
• 发表时间: 2021-05
• 期刊: ArXiv
• 作者: Wenhao Zhan;Shicong Cen;Baihe Huang;Yuxin Chen;Jason D. Lee;Yuejie Chi

SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression

• DOI: 10.48550/arxiv.2206.09888
• 发表时间: 2022-06
• 期刊: ArXiv
• 作者: Zhize Li;Haoyu Zhao;Boyue Li;Yuejie Chi

Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning

打破样本复杂性障碍，实现后悔最优无模型强化学习

• DOI: 10.1093/imaiai/iaac034
• 发表时间: 2023
• 期刊: Information and Inference: A Journal of the IMA
• 作者: Li, Gen;Shi, Laixi;Chen, Yuxin;Chi, Yuejie
• 通讯作者: Chi, Yuejie

Batch Active Learning with Graph Neural Networks via Multi-Agent Deep Reinforcement Learning

• DOI: 10.1609/aaai.v36i8.20897
• 发表时间: 2022-06
• 作者: Yuheng Zhang;Hanghang Tong;Yinglong Xia;Yan Zhu-;Yuejie Chi;Lei Ying

Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis

• DOI: 10.1287/opre.2023.2450
• 发表时间: 2021-02
• 期刊: Operations Research
• 影响因子: 2.7
• 作者: Gen Li;Ee;Changxiao Cai;Yuting Wei