Speeding Up Sparsification using Inner Product Search Data Structures

Zhao Song, Zhaozhuo Xu, Lichen Zhang

Abstract

Iterative sparsification algorithms, such as the Batson-Spielman-Srivastava (BSS) algorithm, are essential for producing optimal linear-sized spectral sparsifiers. However, these methods have historically been limited by high computational costs, specifically an $\Omega(d^4)$ time complexity barrier for deterministic versions. This paper introduces a general framework that leverages efficient inner product search data structures to accelerate the iterative selection process. By reframing vector selection as a data structure query problem, the authors achieve a deterministic running time of $O(d^{\omega+1})$, where $\omega$ is the exponent of matrix multiplication, significantly improving upon prior state-of-the-art results.

Introduction

Sparsification is the process of reducing a large, complex object—such as a graph or a high-dimensional matrix—into a much smaller "sparse" version that preserves its essential spectral properties. In spectral sparsification, the goal is to find a small subset of rows from a matrix $V$ such that the eigenvalues of the original matrix are maintained.

The gold standard for this task is the BSS algorithm, which produces optimal sparsifiers. However, BSS is computationally expensive because it requires searching through all $m$ original vectors at each step to satisfy specific spectral constraints. For years, deterministic implementations were stuck at a computational cost of $\Omega(d^4)$, making them impractical for large-scale datasets. The primary challenge is twofold: efficiently finding the correct vector in each iteration and ensuring search accuracy when queries are adaptive (i.e., when the search at step $t+1$ depends on the result of step $t$).

Methods

The authors address the bottleneck of iterative search by developing three specialized data structure tools:

  1. Positive Inner Product Search (PIPS): A deterministic search tree that stores sums of outer products, allowing the algorithm to find a suitable vector $v_i$ in $O(d^2 \log m)$ time instead of scanning all $m$ vectors.
  2. Minimum Inner Product Search (Min-IPS): Used for discrepancy problems like Kadison-Singer, this tool utilizes a duality between Min-IP and Approximate Furthest Neighbor (AFN) search.
  3. TensorSparse Sketching: A new sketching matrix designed for tensor products ($v \otimes v$). This enables the use of dimensionality reduction (Johnson-Lindenstrauss) while remaining robust against "adaptive adversaries"—scenarios where query choices are non-oblivious.

By integrating these data structures into the BSS framework, the authors transform the brute-force search of each iteration into an efficient query process.

Key Results and Insights

The most significant insight of this work is that the bottleneck in sparsification is not the spectral theory itself, but the search for the next vector. By treating the vector set as a database to be queried, the authors unlock standard acceleration techniques from computational geometry.

As shown in the comparison below, the proposed framework (Theorem 3.1) achieves a running time of $O(d^{\omega+1})$ for deterministic construction. This represents a massive improvement over the previous $O(d^4)$ standard.

Comparison of time complexities for spectral sparsification algorithms across various references, highlighting the improvement in the d exponent.

Beyond spectral sparsification, the authors provided the first fast algorithms for the one-sided Kadison-Singer discrepancy problem and accelerated the "swapping process" used in rounding algorithms for experimental design.

Limitations and Future Work

While $O(d^{\omega+1})$ is theoretically superior, the practical speedup is tied to the efficiency of fast matrix multiplication, where constant factors can be large. Additionally, while this work breaks the deterministic barrier, randomized algorithms using SDP solvers may still be faster in specific graph-based scenarios. The authors suggest that this framework could be extended to other iterative optimization problems, such as sum-of-PSD-matrix sparsification, which remains an open area for further testing.

Summary updated

Abstract

We present a general framework that utilizes different efficient data structures to improve various sparsification problems involving an iterative process. We also provide insights and characterization for different iterative process, and answer that when should we use which data structures in what type of problem. We obtain improved running time for the following problems. * For constructing linear-sized spectral sparsifier (Batson, Spielman and Srivastava, 2012), all the existing deterministic algorithms require $Ω(d^4)$ time. In this work, we provide the first deterministic algorithm that breaks that barrier which runs in $O(d^{ω+1})$ time, where $ω$ is the exponent of matrix multiplication. * For one-sided Kadison-Singer-typed discrepancy problem, we give fast algorithms for both small and large number of iterations. * For experimental design problem, we speed up a key swapping process. In the heart of our work is the design of a variety of different inner product search data structures that have efficient initialization, query and update time, compatible to dimensionality reduction and robust against adaptive adversary.
BibTeX
@misc{song2022speeding,
  author = {Zhao Song and Zhaozhuo Xu and Lichen Zhang},
  title = {{Speeding Up Sparsification using Inner Product Search Data Structures}},
  year = {2022},
  eprint = {2204.03209},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.03209},
}
Figure