A1239
Title: Empirical error estimates for graph sparsification
Authors: Siyao Wang - UC Davis (United States)
Miles Lopes - UC Davis (United States) [presenting]
Abstract: Graph sparsification is a well-established technique for accelerating graph-based learning algorithms, which uses edge sampling to approximate dense graphs with sparse ones. Because the sparsification error is random and unknown, users must contend with uncertainty about the reliability of downstream computations. Although it is possible for users to obtain conceptual guidance from theoretical error bounds in the literature, such results are typically impractical at a numerical level. Taking an alternative approach, these issues are addressed from a data-driven perspective by computing empirical error estimates. The proposed error estimates are highly versatile, and this is demonstrated in four use cases: Laplacian matrix approximation, graph cut queries, graph-structured regression, and spectral clustering. Moreover, two theoretical guarantees for the error estimates are provided, and explanation is given for why the cost of computing them is manageable in comparison to the overall cost of a typical graph sparsification workflow.
