CAREER:Computational Frameworks for Higher-order Graph and Network Data Analysis

Connections in networks are an essential aspect of society, technology, and infrastructure. For example, social connections influence our daily activities, electricity in our homes is delivered by connected power lines, and connections in the brain facilitate our ability to process information. The ability to understand, design, control, and make predictions about these types of connections and networked systems is crucial to improving physical infrastructure, the national defense, and the health of the economy.

This project will develop new artificial intelligence capabilities for leveraging big data coming from connections within a wide range of networks. The key novelty in the research is the direct consideration of connections among several entities at once. For example, connections in small group gatherings affect the spread of disease, connections between multiple drugs are key to many medical treatments, and financial transactions often involve several parties.

By harnessing these multiway connections, we can make improvements to and make discoveries about mechanisms within networks in many settings. For instance, the research has the potential to improve models that forecast disease spread, propose new types of drug combinations, and enhance our ability to detect adversarial and malicious groups on the Web.

This project also involves teaching these ideas in a research-based, interactive summer workshop for college students that is designed to broaden participation in computing-related postgraduate education.

Graphs or networks are a fundamental abstraction for complex relational data throughout the sciences. The basic idea of network models is to represent components of the data by a set of nodes, and to model the relationships among these components using edges that connect pairs of nodes. Computations designed to mine and learn from graph data have resulted in diverse applications within biomedicine, economics, transportation, sociology, and other fields.

However, the focus on pairwise relationships, as encoded by edges in a graph, inherently limits traditional network models. Much of the structure in complex data involves higher-order relationships that take place among more than two entities at once. For example, people communicate in groups over email or text message, students gather in groups in classrooms, and biological interactions occur between a set of molecules rather than just two.

Going beyond graph methods is necessary to fully realize the richness of such higher-order interactions that are pervasive in data. This project ushers in the next generation of network data analysis by directly modeling higher-order interactions in network data and developing data mining and machine learning algorithms for generating meaningful data insights from such models.

The research focuses on three models for higher-order network data, hypergraphs, tensors, and simplicial complexes, which are promising for the way in which they make us think about computations associated with the data. For each model, the project will develop data mining and machine learning methods that offer new insights into network data. These methods will be applied to a variety of real-world data to demonstrate applications in social networks, e-commerce, biomedicine, and information management.

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.