Graph Embeddings via Tensor Products and Approximately Orthonormal Codes
This is an incremental contribution to hyperdimensional computing for graph representation, potentially aiding in compressed storage of large sparse graphs.
The paper tackles the problem of dynamic graph representation by proposing a method based on tensor products and approximately orthonormal codes, showing that it generalizes adjacency matrices and has the same memory-capacity scaling as the Hadamard-Rademacher scheme.
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.