Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.08439 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909328297951232 |
|---|---|
| author | Floros, Dimitris Pitsianis, Nikos Sun, Xiaobai |
| author_facet | Floros, Dimitris Pitsianis, Nikos Sun, Xiaobai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08439 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algebraic Vertex Ordering of a Sparse Graph for Adjacency Access Locality and Graph Compression Floros, Dimitris Pitsianis, Nikos Sun, Xiaobai Data Structures and Algorithms 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. |
| title | Algebraic Vertex Ordering of a Sparse Graph for Adjacency Access Locality and Graph Compression |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.08439 |