Random Projections of Sparse Adjacency Matrices
Not on the map. Why?
Abstract (arXiv)
We analyze a random projection method for adjacency matrices, studying its utility in representing sparse graphs. We show that these random projections retain the functionality of their underlying adjacency matrices while having extra properties that make them attractive as dynamic graph representations. In particular, they can represent graphs of different sizes and vertex sets in the same space, allowing for the aggregation and manipulation of graphs in a unified manner. We also provide results on how the size of the projections need to scale in order to preserve accurate graph operations, showing that the size of the projections can scale linearly with the number of vertices while accurately retaining first-order graph information. We conclude by characterizing our random projection as a distance-preserving map of adjacency matrices analogous to the usual Johnson-Lindenstrauss map.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 6 of its 20 references that are in the map. First posted on arXiv 4 Sep 2023.
Builds on
6 of 20 references.
References · 6
- 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
- 2015Holographic Embeddings of Knowledge Graphscited by 181
- 2021A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part II: Applications, Cognitive Models, and Challengescited by 68
- 2019Fast and Accurate Network Embeddings via Very Sparse Random Projectioncited by 29
- 2022GraphHD: Efficient graph classification using hyperdimensional computingcited by 28
- 2022Graph Embeddings via Tensor Products and Approximately Orthonormal Codescited by 2
Built on by
Not cited yet.