Abstract: 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.

@article{peysakhovich-2022,
  title = {Pseudo-Euclidean Attract-Repel Embeddings for Undirected Graphs},
  author = {Peysakhovich, Alexander and Bottou, Leon},
  journal = {arXiv preprint arXiv:2106.09671},
  year = {2021},
  url = {http://leon.bottou.org/papers/peysakhovich-2022},
}