# Graph Embeddings via Tensor Products and Approximately Orthonormal Codes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 18 Aug 2022.

## Builds on (most cited first, 8 of 8)

- [Holographic Embeddings of Knowledge Graphs](https://mlsanity.com/paper/1510.04935/) (2015)
- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part II: Applications, Cognitive Models, and Challenges](https://mlsanity.com/paper/2112.15424/) (2021)
- [Superposition of many models into one](https://mlsanity.com/paper/1902.05522/) (2019)
- [A comparison of Vector Symbolic Architectures](https://mlsanity.com/paper/2001.11797/) (2020)
- [A Theoretical Perspective on Hyperdimensional Computing](https://mlsanity.com/paper/2010.07426/) (2020)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Logistic Tensor Factorization for Multi-Relational Data](https://mlsanity.com/paper/1306.2084/) (2013)
- [SHEARer: Highly-Efficient Hyperdimensional Computing by Software-Hardware Enabled Multifold Approximation](https://mlsanity.com/paper/2007.10330/) (2020)

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

- [Tensor Products and Hyperdimensional Computing](https://mlsanity.com/paper/2305.10572/) (2023)
- [Random Projections of Sparse Adjacency Matrices](https://mlsanity.com/paper/2309.01360/) (2023)

## Abstract (arXiv)

We propose a dynamic graph representation method, showcasing its rich representational capacity and establishing some of its theoretical properties. Our representation falls under the bind-and-sum approach in hyperdimensional computing (HDC), and we show that the tensor product is the most general binding operation that respects the superposition principle employed in HDC. We also establish some precise results characterizing the behavior of our method, including a memory vs. size analysis of how our representation's size must scale with the number of edges in order to retain accurate graph operations. True to its HDC roots, we also compare our graph representation to another typical HDC representation, the Hadamard-Rademacher scheme, showing that these two graph representations have the same memory-capacity scaling. We establish a link to adjacency matrices, showing that our method is a pseudo-orthogonal generalization of adjacency matrices. In light of this, we briefly discuss its applications toward a dynamic compressed representation of large sparse graphs.