Collaborative Research: III: Small: Taming Large-Scale Streaming Graphs in an Open World

数据在形成社会决策和科学结论方面发挥着至关重要的作用。随着可用数据的丰富，许多数据密集型应用程序都涉及具有底层结构的数据。图提供了一种自然的数学语言来精确地描述这种结构。图形数据在我们的日常生活中无处不在，在水文系统、交通网络、蜂窝网络、社交媒体和网络等许多领域都有发现。图学习（GL）是一个重要的研究领域，专注于处理图信号和在图数据上建立预测模型，并已成为统计建模、数据科学、数据挖掘、机器学习和计算机科学的一个关键主题。传统的GL算法虽然取得了长足的进步，但通常假设图数据的重要因素在学习过程中保持不变。这种静态和封闭的假设倾向于为现实世界中的复杂任务提供过于简化的抽象，使得GL模型无法描述和表达由不断发展的自然或社会现象产生的数据。该项目的首要目标是为这些核心问题提供通用的解决方案。该项目研究的具体应用包括开发更好的方法来监测水体损害，及时发现恶意行为和网络攻击。这个项目也将为计算机科学的研究生和本科生研究人员提供培训机会。将特别强调性别多样性和代表性不足群体的参与，允许来自不同背景的个人为GL研究的进步做出贡献。这个合作项目旨在建立一个全新的、整体的、标准化的图形学习（GL）框架。该项目专注于开放世界和流网络（OWSN）学习，它考虑了图数据随时间的四个关键因素的演变：节点特征、拓扑结构、目标标签和图域。为了实现这一目标，该项目寻求解决基本挑战，并回答在两个线程中对齐的研究问题。第一个线程是图表示，其目的是回答一些基本问题，例如如何使用向量表示来描述具有复杂和不断增长的内容的节点，以及如何描述驱动图拓扑进化的底层过程。第二个线程是图预测建模，它解决了图学习器如何识别新的未知类的出现，并在不牺牲其他已知类的性能的情况下适应它们，以及如何以无监督的方式推广到其他不同的图域。为了解决这些问题，该项目整合了来自不同领域的工具和进展，如在线优化、不确定性量化、变分分析和决策理论。目的是加深对图形数据分析的理解，并为这些领域的相关问题提供新的思路。来自工程应用的真实世界数据，包括水文系统数据和计算机网络数据，将用于广泛评估上述每个主题的进展。与特定应用领域的领域专家合作将确保从该项目中产生的新理论、工具和软件带来有意义的社会效益。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Data plays an essential role in shaping social decisions and scientific conclusions. With the abundance of data available, many data-intensive applications involve data with an underlying structure. Graphs provide a natural mathematical language to precisely describe this structure. Graph data have a ubiquitous presence in our daily lives, found in hydrological systems, transportation networks, cellular networks, social media, and the Web, among many others. Graph Learning (GL) is a crucial research area that focuses on processing graph signals and building predictive models on graph data, and has become a key topic in statistical modeling, data science, data mining, machine learning, and computer science in general. Despite considerable progress, traditional GL algorithms commonly assume that the important factors of the graph data remain unchanged during the learning process. Such static and closed assumptions tend to offer an overly simplified abstraction of complicated tasks in the real world, making GL models fail to characterize and express the data generated from natural or societal phenomena that constantly evolve. The project’s overarching goal is to provide generic solutions to these core issues. Specific applications studied in this project include the development of better approaches for monitoring waterbody impairment and detecting malicious behaviors and cyber-attacks in a timely manner. This project will also provide training opportunities for both graduate and undergraduate researchers in computer science. There will be a specific emphasis on gender diversity and participation of underrepresented groups, allowing individuals from diverse backgrounds to contribute to the advancement of GL research.This collaborative project aims to build a new, holistic, and standardized Graph Learning (GL) framework. The project focuses on open-world and streaming network (OWSN) learning, which considers the evolution of graph data over time in four critical factors: nodal features, topological structures, target labels, and graph domains. To achieve this goal, the project seeks to address fundamental challenges and answer research questions aligned in two threads. The first thread is Graph Representation, which aims to answer fundamental questions such as how to characterize nodes with complex and ever-growing contents using vector representations, and how to delineate the underlying process that drives the evolution of graph topologies. The second thread is Graph Predictive Modeling, which addresses how a graph learner can identify the emergence of new and unknown classes and adapt to them without sacrificing performance on other known classes, and how to generalize to other disparate graph domains in an unsupervised manner. To address these questions, the project integrates tools and advances from diverse areas, such as online optimization, uncertainty quantification, variational analysis, and decision theory. The aim is to deepen the understanding of graph data analysis and shed new light on related questions in these areas. Real-world data from engineering applications, including hydrological system data and computer network data, will be used to extensively evaluate progress in each of the above themes. Collaboration with domain experts in the specified application areas will ensure that the new theory, tools, and software emerging from this project lead to meaningful societal benefits.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.