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

Purdue University, West Lafayette IN

Investigators

Abstract

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.