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

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

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.