III: Small: Nonlinear Processes for Detailed and Principled Insight into Graph Data

网络系统，如道路网络、飞行网络、信息网络和社会网络是社会的重要组成部分。此外，细胞网络作为生物内部的系统一起活动，这些生物本身在生态系统网络中相互作用。了解这些系统的各个部分以及它们如何参与到整个网络中，对于社会学、生物学和神经科学等许多科学和工程领域都是至关重要的。这项基础科学研究要求科学家们有易于使用的工具来研究这些系统。特别是，找到这些系统的各个部分并绘制这些系统的图像的工具。特别是图片，对于传达关于网络的见解非常有帮助。有两种常见的数学和计算工具来完成这些任务。第一类是基于简单的方程集合，这些方程可以用已经研究了很长时间的方法很容易地求解。它们使用直观的物理概念，如染料在水中扩散。第二类，也是最近的一类工具，涉及更复杂的技术，可以模拟大脑的数学抽象。最近的工作展示了第二类工具，可以更好地洞察网络系统。但这样做的代价是，这些工具使人们很难理解它们是如何工作的以及为什么工作的。这与第一节课的内容有很大的不同，第一节课的内容简单易懂。这个奖项的主要目的是研究一类介于两者之间的工具。它结合了第一类的物理直觉和一个简单的改变，使其能够产生像第二类那样的结果。这项研究是理解这些网络如何工作的整体科学努力的重要组成部分。这些网络系统的数学抽象是一个图，这些发现结构的工具通常被称为图挖掘方法。上面讨论的第一类工具是基于线性系统和特征向量的。这些方法通常用作基准，并且有许多有用的直觉来指导它们的应用。最近在高级图神经网络和嵌入技术方面的创新，在第二类中，已经大大提高了这些基准，跨越各种各样的图挖掘任务。这些新方法更强大，但更难以推理。本研究的重点是通过引入线性系统和特征向量算法的简单非线性自适应，在这两种情况之间找到一个机会，这两种算法都与神经网络算法竞争，并且仍然易于推理。这项研究涵盖了四种不同的非线性思想的应用方式。首先，对高度直观的物理过程（如染料在水中扩散）进行了简单的非线性推广，从而提高了性能。这里的一个挑战是，这些需要快速和可靠的算法，使图挖掘容易。其次，图回归试图将数据拟合到网络的顶点和边缘。本奖项的研究涉及研究一个常见回归问题的简单非线性变换。第三，许多基于线性系统的图挖掘工具都有涉及简单线性函数组合的解释。在这里，研究试图用非线性函数代替这些线性函数。第四，对具有数百万个顶点和边的图形进行有用的可视化仍然是一个挑战。该奖项将研究简单的非线性变换如何创建直观的网络可视化。这项研究的主要成果将以算法和方法以及描述它们的论文的形式出现，这些算法和方法描述了在网络上运行的简单非线性过程的挑战和机遇。研究人员还计划发布软件来计算或近似网络上新的简单非线性过程，使其广泛使用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Networked systems such as road networks, flight networks, information networks, and social networks are critical pieces of society. Moreover, networks of cells behave together as systems within living things, and these living things themselves interact in ecosystem networks. Understanding the pieces of these systems and how they participate in the overall network is fundamental to many areas of science and engineering ranging from sociology, biology, and neuroscience. This fundamental scientific study requires that scientists have easy-to-use tools to study these systems. In particular, tools to find pieces of these systems and to draw pictures of these systems. Pictures, in particular, are extremely helpful to communicate insights about the networks. There are two common types of mathematical and computational tools to accomplish these tasks. The first class is based on simple collections of equations that can be easily solved using methods that have been studied for a long time. These use intuitive physical ideas such as dye spreading in water. The second, and more recent, class of tools involves more complicated techniques that mimic mathematical abstractions of the brain. Recent work has shown the second class of tools to provide better insights into the networked systems. But this comes at the price that the tools make it hard to understand how and why they work. This is very different from those in the first class, which are easy and intuitive to understand. The main aim of this award is to investigate a class of tools that falls between the two. It combines the physical intuition of the first class with a simple change that gives the ability to produce results like the second class. This study is an important component of the overall scientific effort to understand how these networks work. The mathematical abstraction underlying these networks systems is a graph and these tools to find structure are often called graph mining methods. The first class of tools discussed above is based on linear systems and eigenvectors. These methods are often used as benchmarks and have many helpful intuitions to guide their application. Recent innovations in advanced graph neural network and embedding techniques, those in the second class, have considerably improved on these benchmarks across a wide variety of graph mining tasks. These new methods are more powerful but are harder to reason about. The focus of this research is to navigate an opportunity between these two scenarios by introducing simple nonlinear adaptations of the linear system and eigenvector algorithms that are both competitive with neural network algorithms and remain easy to reason about. The investigation covers four different ways the nonlinear idea could be used. First, there are simple nonlinear generalizations of highly intuitive physical processes such as dye spreading in water that give improved performance. A challenge here is that these need fast and reliable algorithms to make graph mining easy. Second, a graph regression seeks to fit data to the vertices and edges of a network. The research in this award involves studying a simple nonlinear transform of common regression problems. Third, many graph mining tools based on linear systems have interpretations that involve a combination of simple linear functions. Here, the study seeks to replace these linear functions with nonlinear functions. Fourth, producing a useful visualization of a graph with millions of vertices and edges remains a challenge. This award will investigate how simple nonlinear transformations create intuitive network visualizations. The primary outcomes from this research will be in the form of algorithms and methods, as well as papers describing them, that characterize the challenges and opportunities of simple nonlinear processes run on networks. The investigator also plans to release software to compute or approximate the new simple nonlinear processes on networks to make them widely available.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.