Sparse graph based sketching for fast numerical linear algebra

Dong Hu, Shashanka Ubaru, Alex Gittens, Kenneth L. Clarkson, Lior Horesh, Vassilis Kalantzis

Abstract

Sketching is a critical technique for compressing massive datasets to facilitate efficient numerical linear algebra. However, traditional dense sketching matrices, such as Gaussian matrices, incur high computational costs during the sketching process. This paper introduces a novel class of sketching matrices derived from sparse bipartite graphs, specifically expander and magical graphs. We provide theoretical guarantees that these sparse constructions satisfy the $(1 \pm \epsilon)$ $\ell_2$-subspace embedding property. Empirical evaluations on synthetic and real-world datasets (Movielens, Jester, CRAN) demonstrate that these graph-based sketches achieve accuracy comparable to dense methods while significantly reducing computational complexity. Notably, magical graphs with a left degree of $s=2$ provide a robust balance between sparsity and stability.

Introduction

The proliferation of Big Data has necessitated the development of efficient algorithms for processing massive matrices. Fundamental tasks like least-squares regression and low-rank matrix approximation become bottlenecked by the dimensions of the input data. Sketching addresses this by projecting a large matrix $A$ into a lower-dimensional space via a random matrix $S$, creating a "sketch" $SA$ that preserves the original matrix's geometric properties.

Traditional sketching matrices, while theoretically sound, often suffer from density, making the computation of $SA$ expensive. While sparse alternatives like CountSketch ($s=1$) exist, they can lack the stability required for certain applications. This work explores the use of highly sparse bipartite graphs to construct sketching matrices that are both fast and accurate.

Methods: Graph-Based Sketching

The proposed sketching matrices are based on the adjacency matrices of two types of sparse bipartite graphs: Magical Graphs and Expander Graphs.

  1. Magical Graphs: These graphs are characterized by the property that small subsets of nodes on the left side have a high probability of unique matchings to the right side. We find that a left degree of $s=2$ is particularly effective for balancing speed and accuracy.
  2. Expander Graphs: These are sparse graphs with high connectivity, ensuring that any set of nodes has a disproportionately large neighborhood.
Bipartite graph representation of an expander sketch.

The theoretical contribution of this work is the proof that these graph-based matrices provide $(1 \pm \epsilon)$ $\ell_2$-subspace embeddings. This means the sketch does not distort the lengths of vectors in a specific subspace by more than a small factor $\epsilon$. Furthermore, by utilizing expanders derived from error-correcting codes (ECC), we can construct "almost deterministic" sketches that require minimal random seed information, which is advantageous for hardware implementations.

Results and Empirical Evaluation

We evaluated the performance of these sparse sketches against standard baselines, including Gaussian Sketch, CountSketch, and Subsampled Randomized Fourier/Hadamard Transforms (SRFT/SRHT). The methods were tested on synthetic Gaussian matrices ($4096 \times 1000$) and real-world datasets including Movielens 100k, Jester, and CRAN (LSI).

Performance comparison of graph-based sketches against traditional methods.

As illustrated in Figure 2, the distortion error for both Magic Graphs and expander-based sketches converges rapidly as the sketching size $m$ increases. The performance of the $s=2$ Magic Graph is particularly noteworthy, as it tracks the accuracy of dense Gaussian sketches while maintaining the speed advantages of sparsity. Tests on real-world datasets like Movielens and Jester confirmed these findings, showing that sparse graph-based sketches can replace dense ones with negligible loss in accuracy.

Conclusion

This research demonstrates that the expansion properties of sparse bipartite graphs can be directly translated into high-quality dimensionality reduction sketches. By moving from $s=1$ to $s=2$ in sparse constructions, we achieve a significant gain in stability without sacrificing computational speed. Future research will investigate the behavior of these sketches with nonlinear operators common in deep learning and their applicability to non-Euclidean norms like $\ell_1$.

Summary updated

Abstract

In recent years, a variety of randomized constructions of sketching matrices have been devised, that have been used in fast algorithms for numerical linear algebra problems, such as least squares regression, low-rank approximation, and the approximation of leverage scores. A key property of sketching matrices is that of subspace embedding. In this paper, we study sketching matrices that are obtained from bipartite graphs that are sparse, i.e., have left degree~s that is small. In particular, we explore two popular classes of sparse graphs, namely, expander graphs and magical graphs. For a given subspace $\mathcal{U} \subseteq \mathbb{R}^n$ of dimension $k$, we show that the magical graph with left degree $s=2$ yields a $(1\pm \epsilon)$ ${\ell}_2$-subspace embedding for $\mathcal{U}$, if the number of right vertices (the sketch size) $m = \mathcal{O}({k^2}/{\epsilon^2})$. The expander graph with $s = \mathcal{O}({\log k}/{\epsilon})$ yields a subspace embedding for $m = \mathcal{O}({k \log k}/{\epsilon^2})$. We also discuss the construction of sparse sketching matrices with reduced randomness using expanders based on error-correcting codes. Empirical results on various synthetic and real datasets show that these sparse graph sketching matrices work very well in practice.
BibTeX
@inproceedings{hu2021sparse,
  author = {Dong Hu and Shashanka Ubaru and Alex Gittens and Kenneth L. Clarkson and Lior Horesh and Vassilis Kalantzis},
  title = {{Sparse graph based sketching for fast numerical linear algebra}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=S9UZv1Foje9},
}
Figure