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

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

• 批准号: 2134081
• 负责人: Lei Ying
• 金额: $ 35万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-01-01 至 2024-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2134081&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.

图形学习已成为许多现实世界应用中的基石，例如社交媒体采矿，大脑连通性分析，计算流行病学和财务欺诈检测。图形神经网络（简称GNNS）代表了深度图学习模型的重要且新兴的家族。通过产生图形元素的向量表示，GNN在很大程度上简化了许多图形学习问题。在绝大多数现有作品中，它们需要给定的图，包括其拓扑，相关的属性信息和（半）监督学习任务的标签，这是相应学习模型的输入的一部分。尽管取得了巨大的进步，但仍缺少最佳深图学习的理论基础，该项目旨在实现这一差距。该项目的结果对教育和社会产生了更大的影响。该项目的结果丰富了课程以及参与机构的夏季推广计划，并通过各种格式进一步传播到社区，以创造协同作用并提高对不同学科的理解。该项目受益于各种基于图形学习的应用程序，包括建议，电网，神经科学，团队科学和管理以及智能运输系统。该项目在图神经网络中研究了输入数据的基本作用，包括图形拓扑，属性和可选标签。该项目中有三个研究作用。第一个推力试图了解GNNS模型对输入图的敏感程度。如何量化GNNS模型的不确定性；以及这如何影响GNNS模型的概括性能。第二个推力开发了算法来优化最初提供的图形，以最大程度地提高给定GNNS模型的概括性能。第三个推力基于熵正则化的深入增强学习开发了主动学习方法，以最佳获取其他标签，以进一步改善GNNS模型。该项目根据图形神经网络的灵敏度，不确定性和概括性能研究了新的理论基础。它开发了新的算法来学习最佳图形和具有更好效率的主动GNN，其基本限制（包括样本复杂性，概括错误限制，最佳和融合率）已充分理解。该奖项反映了NSF的法定任务，并通过基金会的知识优点和广泛的影响来评估NSF的法定任务，并被认为是值得的支持。

项目成果

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

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

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

Provably Efficient Model-Free Algorithms for Non-stationary CMDPs

• DOI: 10.48550/arxiv.2303.05733
• 发表时间: 2023-03
• 期刊: ArXiv
• 作者: Honghao Wei;A. Ghosh;N. Shroff;Lei Ying;Xingyu Zhou