Spectral Sparsification of Metrics and Kernels

A set of n points in a geometric space implicitly induces a complete graph where the weight of an edge between two points is a function of the distance between the endpoints. There are many natural problems that arise from such a geometric graph and many standard geometric problems can be recast as simple properties of this graph. A basic algorithmic obstacle that arises is that the explicit size of the graph is quadratic in the size of the input. There is a long line of research overcoming this obstacle in low-dimensional spaces, as well as some positive results in high-dimensional and more abstract models for specific applications. Here we consider graph problems in general and address the issue of constructing the geometric graph. Rather than constructing these graphs exactly, we ask if it is possible to explicitly construct a sparse approximation of these geometric graphs in nearly linear time. We consider geometric graphs where the edge weights are given as either as a metric (via an oracle), or given by a smooth kernel function in a Euclidean space. For both of these settings, we show that for any ∊ > 0, one can compute an explicit (1 + ∊)-approximate spectral approximation of the geometric graph with Õ(n/∊2) edges in Õ(n/∊2) randomized time. Some of these algorithms are extremely simple. Composed with nearly linear time graph algorithms, this allows for a broad class of applications on geometric graphs with running times proportional to the number of points.