2022/08/18 by Frank Qiu, Qiu, Frank
Computer Science · Engineering · #68P02 #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel Computing and Optimization Techniques #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2208.10917
openalex publication_date 2022/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.