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

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

• 批准号: 2134079
• 负责人: Hanghang Tong
• 金额: $ 35万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-01-01 至 2024-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2134079&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模型对输入图的敏感程度;如何量化GNNs模型的不确定性;以及这如何影响GNNs模型的泛化性能。第二个推力开发算法来优化最初提供的图，以便最大限度地提高给定GNNs模型的泛化性能。第三个目标是开发基于深度强化学习和熵正则化的主动学习方法，以最佳方式获得额外的标签，从而进一步改进GNNs模型。本计画针对图类神经网路的灵敏度、不确定性与泛化性能，探讨新的理论基础。它开发了新的算法，用于学习最优图和主动GNN，具有更好的效率，其基本限制，包括样本复杂性，泛化误差界，最优性和收敛速度，都得到了很好的理解。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Domain Adaptation in Physical Systems via Graph Kernel

• DOI: 10.1145/3534678.3539380
• 发表时间: 2022-08
• 期刊: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
• 作者: Haoran Li;H. Tong;Yang Weng

YACC: A Framework Generalizing TuránShadow for Counting Large Cliques

YACC：用于计算大派系的泛化 TuránShadow 的框架

• 发表时间: 2022
• 期刊: SDM2022
• 作者: Shweta Jain, Hanghang Tong

Graph Sanitation with Application to Node Classification

• DOI: 10.1145/3485447.3512180
• 发表时间: 2021-05
• 期刊: Proceedings of the ACM Web Conference 2022
• 作者: Zhe Xu;Hanghang Tong

Joint Knowledge Graph Completion and Question Answering

• DOI: 10.1145/3534678.3539289
• 发表时间: 2022-08
• 期刊: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
• 作者: Lihui Liu;Boxin Du;Jiejun Xu;Yinglong Xia;H. Tong

JuryGCN: Quantifying Jackknife Uncertainty on Graph Convolutional Networks

• DOI: 10.1145/3534678.3539286
• 发表时间: 2022-08
• 期刊: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
• 作者: Jian Kang;Qinghai Zhou;H. Tong