CAREER: Fast algorithms via a spectral theory for graphs with a prescribed cut structure

Critical applications involving very large data sets require algorithms that run fast and provide strong performance guarantees. Among the numerous examples are the analysis of medical scans and the acquisition -via imaging- of connectivity in neural systems, an important task in current computational neuroscience. These problems are very often approached by first modeling the data as networks -also called graphs- and then applying graph-specific algorithms to solve them. Among many possibilities, algorithms that rely on certain algebraic representations of graphs have become very appealing due to recent theoretical progress that renders them very time-efficient. However, efficiency appears to come at the cost of an occasionally inferior quality in the generated solutions. Via the proposed extensions of the theory studying these algebraic representations, the project will design new algorithms with strong guarantees and wide applicability.

Spectral graph theory studies the connections between algebraic and combinatorial properties of graphs. It is well known that these connections can be far from tight. For example, two given graphs may have approximately the same cuts, but significantly different eigenvalues and eigenvectors. As a result, spectral algorithms for cut problems on graphs, albeit very fast, do not provide good approximation guarantees. This project will extend aspects of spectral graph theory to a spectral theory for cut structures, defined as sets of graphs with approximately prescribed cuts. The central question of the new theory is: What kind of spectral properties can be realized by graphs within a given cut structure?

A goal of the project is to show that any cut structure contains graphs whose eigenvectors provide tight information about its cuts. The project will also study algorithms for the efficient computation of these special graphs, by essentially modifying the spectrum of an input graph without significantly altering its cuts. Then, the combination of spectral modification and classical spectral algorithms will yield fast algorithms with enhanced approximation guarantees. The project will draw from connections of spectral graph theory with graph decompositions discovered in the context of oblivious routing algorithms. In turn, it is expected that the project will have an impact on routing problems too. In later stages the project will study the theoretical limits of spectral modification. It will also examine the descriptive quality of the developed theory in the performance of algorithms and other phenomena on interesting classes of graphs, such as social or biological networks.

The project will freely disseminate prototype implementations of the new algorithms and will apply them to computer vision and machine learning problems in industry and academia. Applications will be pursued via selected interdisciplinary collaborations. The balance between theoretical and applied work will serve a broader educational effort at both the undergraduate and graduate level, which will also include the introduction of new courses. A significant part of the research will be carried out at the University of Puerto Rico, and so the project is expected to have a significant impact in the education of underrepresented minorities.