TCS+ Talk

Abstract: Problems arising from analyzing and understanding graph structures have motivated the development of many powerful tools for storing and compressing graphs and networks. Many, if not most, of these massive graphs are accumulations of updates over time. Maintaining updates and queries on dynamically changing graphs more efficiently than recomputing from scratch is a well-studied topic, with several important open problems related to global, optimization related queries.

We study dynamic graph algorithms for maintaining spectral vertex sparsifiers with respect to a subset of terminal vertices. Such sparsifiers preserve key structures in spectral algorithms, including effective resistances (which can be viewed as a numerical generalization of connectivity), solutions to systems of Laplacian linear equations, and energy of electrical flows between terminal vertices. We give data structures that maintain, in sublinear time, these sparsifiers under insertions/deletions of edges, as well as terminal additions.

This primitive in turn leads to sublinear time data structures for key primitives in spectral graph algorithms, including ones at the core of the `Laplacian paradigm' for designing graph optimization algorithms. In particular, we obtain O(m^{4/3}\epsilon^{-4}) time per query/update for effective resistances on unweighted graphs, and O(n^{11/12}\epsilon^{-5}) time per query/update for implicit access to linear system solutions, where \epsilon is the relative approximation accuracy.

The majority of the talk will focus on key components of this data structure: (1) an interpretation of vertex sparsifiers as a sum of random walks, (2) a suitable choice of terminals to keep these walks local, and (3) maintenance of local walks and numerical solutions. Potential avenues in generalizing these techniques to provide new building blocks for dynamic graph algorithms will also be discussed.