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 在很大程度上简化了许多图学习问题。在绝大多数现有工作中，它们需要给定的图，包括其拓扑、相关属性信息和（半）监督学习任务的标签，作为相应学习模型输入的一部分。尽管取得了巨大进展，但最佳深度图学习的理论基础仍然缺失，而该项目旨在填补这一空白。该项目的成果对教育和社会产生更广泛的影响。该项目的成果丰富了参与机构的课程和暑期外展项目，并通过多种形式进一步向社区传播，以产生协同效应并增进对不同学科的理解。该项目有利于各种基于图学习的高影响力应用，包括推荐、电网、神经科学、团队科学和管理以及智能交通系统。该项目研究了输入数据的基本作用，包括图拓扑、属性和图神经网络中的可选标签。该项目共有三个研究重点。第一个主旨旨在了解 GNN 模型对于输入图的敏感程度；如何量化GNNs模型的不确定性；以及这如何影响 GNN 模型的泛化性能。第二个推动力开发算法来优化最初提供的图，以最大限度地提高给定 GNN 模型的泛化性能。第三个重点是开发基于深度强化学习和熵正则化的主动学习方法，以最佳地获得附加标签，以进一步改进 GNN 模型。该项目研究图神经网络的敏感性、不确定性和泛化性能方面的新理论基础。它开发了用于学习最优图和具有更好功效的主动 GNN 的新算法，其基本限制，包括样本复杂性、泛化误差界限、最优性和收敛速度，都是众所周知的。该奖项反映了 NSF 的法定使命，并通过评估认为值得支持利用基金会的智力优势和更广泛的影响审查标准。

项目成果

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

正则化强化学习的策略镜像下降：具有线性收敛的广义框架

• DOI: 10.1137/21m1456789
• 发表时间: 2023-06
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: Zhan, Wenhao;Cen, Shicong;Huang, Baihe;Chen, Yuxin;Lee, Jason D.;Chi, Yuejie
• 通讯作者: Chi, Yuejie

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

Q-Learning Minimax 是最优的吗？

• DOI: 10.1287/opre.2023.2450
• 发表时间: 2024-01
• 期刊: Operations Research
• 影响因子: 2.7
• 作者: Li, Gen;Cai, Changxiao;Chen, Yuxin;Wei, Yuting;Chi, Yuejie
• 通讯作者: Chi, Yuejie

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

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

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

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

SoteriaFL：具有通信压缩功能的私有联合学习的统一框架

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

Active Heterogeneous Graph Neural Networks with Per-step Meta-Q-Learning

具有每步 Meta-Q-Learning 的主动异构图神经网络

• DOI: 10.1109/icdm54844.2022.00176
• 发表时间: 2022-11-01
• 期刊: 2022 IEEE International Conference on Data Mining (ICDM)
• 作者: Yuheng Zhang;Yinglong Xia;Yan Zhu;Yuejie Chi;Lei Ying;H. Tong
• 通讯作者: H. Tong