# Algebraic Vertex Ordering of a Sparse Graph for Adjacency Access Locality and Graph Compression

arXiv: https://arxiv.org/abs/2408.08439 · HTML: https://mlsanity.com/paper/2408.08439/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2024.

## Built on by (most cited first, 2 of 2)

- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Mixing Configurations for Downstream Prediction](https://mlsanity.com/paper/2510.19248/) (2025)

## Abstract (arXiv)

In this work, we establish theoretical and practical connections between vertex indexing for sparse graph/network compression and matrix ordering for sparse matrix-vector multiplication and variable elimination. We present a fundamental analysis of adjacency access locality in vertex ordering from the perspective of graph composition of, or decomposition into, elementary compact graphs. We introduce an algebraic indexing approach that maintains the advantageous features of existing methods, mitigates their shortcomings, and adapts to the degree distribution. The new method demonstrates superior and versatile performance in graph compression across diverse types of graphs. It also renders proportional improvement in the efficiency of matrix-vector multiplications for subspace iterations in response to random walk queries on a large network.