Graph Embeddings via Tensor Products and Approximately Orthonormal Codes

We introduce a method for embedding graphs as vectors in a structure-preserving manner, showcasing its rich representational capacity and giving some theoretical properties. Our procedure falls under the bind-and-sum approach, and we show that our binding operation - the tensor product - is the most general binding operation that respects the principle of superposition. We also establish some precise results characterizing the behavior of our method, and we show that our use of spherical codes achieves a packing upper bound. Then, we perform experiments showcasing our method's accuracy in various graph operations even when the number of edges is quite large. Finally, we establish a link to adjacency matrices, showing that our method is, in some sense, a generalization of adjacency matrices with applications towards large sparse graphs.