We are thrilled to welcome Prof. Miles Lopes for a talk on Empirical Error Estimates for Graph Sparsification.
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, we propose to address these issues from a data-driven perspective by computing empirical error estimates. The proposed error estimates are highly versatile, and we demonstrate this in four use cases: Laplacian matrix approximation, graph cut queries, graph-structured regression, and spectral clustering. Moreover, we provide two theoretical guarantees for the error estimates, and explain why the cost of computing them is manageable in comparison to the overall cost of a typical graph sparsification workflow. (Joint work with Siyao Wang)
About the Speaker: Miles Lopes is an Associate Professor in the Department of Statistics at UC Davis, where he is also affiliated with the Graduate Group in Applied Mathematics (GGAM). He received his Ph.D. in Statistics from UC Berkeley, under the supervision of Peter J. Bickel. His research focuses on high-dimensional statistics and machine learning, with particular interests in bootstrap methods for complex data settings and error analysis of randomized algorithms. His recent work includes topics such as robust inference, spectral methods, and practical error guarantees for graph-based learning.