A graphon-based approach to seriation and an application in GSP

University Of Delaware, Newark DE

Investigators

Abstract

This is an age of data, much of which is in the form of large networks, such as social networks, biological networks, or neural cell networks. These real-life networks are very complex, and understanding their structure is crucial for developing robust and efficient algorithms on them. The Principal Investigator (PI) aims to develop a systematic mathematical approach for analyzing and visualizing large networks. By integrating two different areas of mathematics, namely Discrete Mathematics and Analysis, the PI plans to extract large-scale features of networks using mathematical limit theories. Potential practical applications of this research include diverse instances such as data analysis in sociology, psychology, and image processing. Additionally, the PI is dedicated to teaching and training graduate and undergraduate students. To support this, the PI will supervise student research on problems related to this topic. Moreover, the PI will organize two events at the University of Delaware: one for high school students and another for undergraduate students. A fundamental problem in the analysis of networks is to uncover their ‘hidden spatial layout’, i.e. to label their vertices according to the spatial features of the network. This is the well-known seriation problem, a challenging problem in machine learning. In recent years, various heuristics and algorithms for the approximate versions of the seriation problem have been developed, but there is little theoretical evidence for why these methods should perform successfully or how they can be extended to the multi-dimensional case. Here, we discuss several intriguing and challenging questions regarding robustness/consistency of spectral seriation and its generalizations to higher dimensions. Graphons offer a non-parametric approach to network modeling, that is highly valuable when studying stochastic networks. Employing the powerful theory of dense/sparse graph limits, the PI plans to answer questions about stochastic networks (large discrete structures that vary over time) by inspecting the associated graphons (fundamental limit). To address the multi-dimensional case, the PI will develop a novel robust parameter which measures the extent of n-dim spatiality of a network. The PI will then investigate how spatial graphons can be used to provide instance-independent graph signal processing methods for real-life networks. Moreover, the results of this research will lead to further interactions between graphon theory, functional analysis, and learning theory. 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.