Pseudo-Euclidean Attract-Repel Embeddings for Undirected Graphs
This addresses the limitation of transitivity in graph embeddings for real-world non-transitive relationships, offering a method that can be applied to models like exponential family embeddings or graph neural networks.
The paper tackles the problem of embedding undirected graphs by removing the transitivity assumption in dot product embeddings, using pseudo-Euclidean spaces with attract and repel vectors, resulting in efficient network compression and improved link prediction when integrated into existing models.
Dot product embeddings take a graph and construct vectors for nodes such that dot products between two vectors give the strength of the edge. Dot products make a strong transitivity assumption, however, many important forces generating graphs in the real world lead to non-transitive relationships. We remove the transitivity assumption by embedding nodes into a pseudo-Euclidean space - giving each node an attract and a repel vector. The inner product between two nodes is defined by taking the dot product in attract vectors and subtracting the dot product in repel vectors. Pseudo-Euclidean embeddings can compress networks efficiently, allow for multiple notions of nearest neighbors each with their own interpretation, and can be `slotted' into existing models such as exponential family embeddings or graph neural networks for better link prediction.