Neural embeddings have been used with great success in Natural Language Processing (NLP) where they provide compact representations that encapsulate word similarity and attain state-of-the-art performance in a range of linguistic tasks. The success of neural embeddings has prompted significant amounts of research into applications in domains other than language. One such domain is graph-structured data, where embeddings of vertices can be learned that encapsulate vertex similarity and improve performance on tasks including edge prediction and vertex labelling. For both NLP and graph-based tasks, embeddings in high-dimensional Euclidean spaces have been learned.
 However, recent work has shown that the appropriate isometric space for embedding complex networks is not the flat Euclidean space, but a negatively curved hyperbolic space. We present a new concept that exploits these recent insights and propose learning neural embeddings of graphs in hyperbolic space. We provide experimental evidence that hyperbolic embeddings significantly outperform Euclidean embeddings on vertex classification tasks for several real-world public datasets. Embeddings are used to represent complex high-dimensional data in lower-dimensional continuous spaces BID28 BID3 . Embedded representations provide three principal benefits over sparse schemes: They encapsulate similarity, are compact, and perform better as inputs to machine learning models BID29 . These benefits are particularly important for graph-structured data where the native representation is the adjacency matrix, which is typically a sparse matrix of connection weights.Neural embedding models are a flavour of embedding where the embedded representation corresponds to a subset of the connection weights in a neural network (see FIG2 ), which are learned through backpropagation. Neural embedding models have been shown to improve performance on many tasks across multiple domains, including word analogies (Mikolov et al., 2013a; BID20 , machine translation BID31 ), document comparison (Kusner et al., 2015 , missing edge prediction BID12 , vertex attribution BID26 , product recommendations BID10 BID1 , customer value prediction BID14 BID6 and item categorisation BID2 . In all cases, the embeddings are learned without labels (unsupervised) from a sequence of tokens. Previous work on neural embedding models has either either explicitly or implicitly (by using the Euclidean dot product) assumed that the embedding space is Euclidean. However, recent work in the field of complex networks has found that many interesting networks, particularly those with a scale-free structure such as the Internet BID30 BID5 or academic citations BID8 BID7 can be well described with a geometry which is non-Euclidean, such as hyperbolic geometry. Even more recently the problem of mapping graphs and datasets to a low-dimensional hyperbolic space has been addressed in BID24 and BID4 . Here we use a neural embedding approach based on the Skipgram architecture to find hyperbolic embeddings.There are two reasons why embedding complex networks in hyperbolic geometry can be expected to perform better than Euclidean geometry. The first is that complex networks exhibit a hierarchical structure. Hyperbolic geometry provides a continuous analogue of tree-like graphs, and even infinite trees have nearly isometric embeddings in hyperbolic space BID11 . The second property is that complex networks have power-law degree distributions, resulting in high-degree hub vertices. All tiles are of constant area in hyperbolic space, but shrink to zero area at the boundary of the disk in Euclidean space. c Hub and spokes graph. It is impossible to embed this graph in two-dimensional Euclidean space and preserve the properties that (1) all spokes are the same distance from the hub, (2) all spokes are the same distance from each other, and (3) the distance between spokes along the circumference is more than twice the distance to the hub. In hyperbolic space such embeddings exist. FIG1 shows a simple hub-and-spoke graph where each spoke is a distance R from the hub and 2R from each other. For an embedding in two-dimensional Euclidean space it is impossible to reproduce this geometry for more than two spokes. However, in hyperbolic space, large numbers of spokes that satisfy these geometrical constraints can be embedded because the circumference of a circle expands exponentially rather than polynomially with the radius.The starting point for our model is the celebrated Skipgram architecture (Mikolov et al., 2013a; b) shown in FIG2 . Skipgram is a shallow neural network with three layers: (1) An input projection layer that maps from a one-hot-encoded token to a distributed representation, (2) a hidden layer, and (3) an output softmax layer. Skipgram is trained on a sequence of words that is decomposed into (input word, context word)-pairs. The model uses two separate vector representations, one for the input words and another for the context words, with the input representation comprising the learned embedding. The (input word, context word)-pairs are generated by running a fixed length sliding window over a word sequence. Words are initially randomly allocated to vectors within the two vector spaces. Then, for each training word pair, the vector representations of the observed input and context words are pushed towards each other and away from all other words (see FIG2 ). The model can be extended to network structured data using random walks to create sequences of vertices. Vertices are then treated exactly analogously to words in the NLP formulation. This was originally proposed as DeepWalk BID26 . Extensions varying the nature of the random walks have been explored in LINE BID32 and Node2vec BID12 .Contribution In this paper, we introduce the new concept of neural embeddings in hyperbolic space. We formulate backpropagation in hyperbolic space and show that using the natural geometry of complex networks improves performance in vertex classification tasks across multiple networks. At the same time, BID24 independently proposed a hyperbolic embedding algorithm that has similarities to ours. The key differences are that BID24 try to fit the hyperbolic distance between nodes using cartesian coordinates in the Poincaré disk, whereas we use a modified cosine distance in a spherical hyperbolic coordinate system. Our approach does not require a numerical constraint to prevent points from 'falling off' the edge of the disk and becoming infinitely distant from the others.
We learn neural embeddings of graphs in hyperbolic instead of Euclidean space
{"src": "scitldr-AIC_train", "paper_id": "S1xDcSR6W"}