CAREER: On Non-Linear Graph Eliminations

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

Graphs, being natural abstractions of relationships, are widely used to model data from various scenarios, such as social networks, deep neural networks, and human brain neuron systems. The scientific research community has benefited from the profound expressibility and analysis power of graphs. However, with the explosive growth in the amount of available data, traditional graph algorithms often fall short of efficiency. This project aims to develop faster graph algorithms from the aspect of graph sparsification, which compresses large graphs into small graphs so that computation can be performed on smaller graphs. The goal of this project is to advance graph sparsification as a new paradigm of graph algorithms and to provide new sparsification-based software for graph problems that are crucial to applications in machine learning, data mining, and computational biology. The investigator will incorporate the research closely into education by providing research opportunities for undergraduate and graduate students and integrating the research results into related courses. This project aims to investigate graph vertex sparsification tools that reduce both vertices and edges of graphs while preserving certain graph properties between a subset of vertices. The major challenge of vertex sparsification lies in the fact that the reduction of vertices is difficult to achieve with linear operators, such as Gaussian elimination, which are employed by classic edge reduction. To address this challenge, this project will focus on developing and analyzing non-linear operators, such as combinatorial truncation and non-linear algebraic transform, to construct new vertex sparsifiers for fundamental graph properties. In addition, this project will propose new principles for designing vertex-sparsification-based algorithms. Particularly, this will include incorporating vertex sparsifiers with optimization methods, investigating the interaction between sparsifiers and other structures such as graph decompositions, and identifying the key features of sparsifiers that enable their applications in dynamic, distributed, and parallel settings. 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.