Finding a low dimensional representation of hierarchical, structured data described by a network remains a challenging problem in the machine learning community. An emerging approach is embedding these networks into hyperbolic space because it can naturally represent a network's hierarchical structure. However, existing hyperbolic embedding approaches cannot deal with attributed networks, in which nodes are annotated with additional attributes. These attributes might provide additional proximity information to constrain the representations of the nodes, which is important to learn high quality hyperbolic embeddings. To fill this gap, we introduce HEAT (Hyperbolic Embedding of ATributed networks), the first method for embedding attributed networks to a hyperbolic space. HEAT consists of 1) a modified random walk algorithm to obtain training samples that capture both topological and attribute similarity; and 2) a learning algorithm for learning hyperboloid embeddings from the obtained training samples. We show that by leveraging node attributes, HEAT can outperform a state-of-the-art Hyperbolic embedding algorithm on several downstream tasks. As a general embedding method, HEAT opens the door to hyperbolic manifold learning on a wide range of attributed and unattributed networks.
Beyond the two-dimensional hyperbolic disk, an @math -dimensional Poincar 'e ball can give more degrees of freedom to the embedding and capture further dimensions of attractiveness than just popularity'' and similarity'' @cite_8 @cite_1 . By embedding general graphs to trees, @cite_0 were able to achieve state-of-the-art results by extending the work of @cite_19 .
@cite_0 @cite_19 @cite_1 @cite_8
2797520557 2142420687 2020141201 2199357291
Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures like synonym or type hierarchies. Given a tree, we give a combinatorial construction that embeds the tree in hyperbolic space with arbitrarily low distortion without using optimization. On WordNet, our combinatorial embedding obtains a mean-average-precision of 0.989 with only two dimensions, while 's recent construction obtains 0.87 using 200 dimensions. We provide upper and lower bounds that allow us to characterize the precision-dimensionality tradeoff inherent in any hyperbolic embedding. To embed general metric spaces, we propose a hyperbolic generalization of multidimensional scaling (h-MDS). We show how to perform exact recovery of hyperbolic points from distances, provide a perturbation analysis, and give a recovery result that allows us to reduce dimensionality. The h-MDS approach offers consistently low distortion even with few dimensions across several datasets. Finally, we extract lessons from the algorithms and theory above to design a PyTorch-based implementation that can handle incomplete information and is scalable. We introduce a novel measure called e-four-pointscondition (e-4PC), which assigns a value e ∈ [0,1] to every metric space quantifying how close the metric is to a tree metric. Data-sets taken from real Internet measurements indicate remarkable closeness of Internet latencies to tree metrics based on this condition. We study embeddings of e-4PC metric spaces into trees and prove tight upper and lower bounds. Specifically, we show that there are constants c1 and c2 such that, (1) every metric (X,d) which satisfies the e-4PC can be embedded into a tree with distortion (1+e)c1log|X|, and (2) for every e ∈: [0,1] and any number of nodes, there is a metric space (X,d) satisfying the e-4PC that does not embed into a tree with distortion less than (1+e)c2log|X|. In addition, we prove a lower bound on approximate distance labelings of e-4PC metrics, and give tight bounds for tree embeddings with additive error guarantees. We introduce a novel projection-based visualization method for high-dimensional data sets by combining concepts from MDS and the geometry of the hyperbolic spaces. This approach hyperbolic multi-dimensional scaling (H-MDS) is a synthesis of two important concepts for explorative data analysis and visualization: (i) multi-dimensional scaling uses proximity or pair distance data to generate a low-dimensional, spatial presentation of the data; (ii) previous work on the "hyperbolic tree browser" demonstrated the extraordinary advantages for an interactive display of graph-like data in the two-dimensional hyperbolic space (H2).In the new approach, H-MDS maps proximity data directly into the H2. This removes the restriction to "quasihierarchical", graph-based data--a major limitation of (ii). Since a suitable distance function can convert all kinds of data to proximity (or distance-based) data, this type of data can be considered the most general.We review important properties of the hyperbolic space and, in particular, the circular Poincare model of the H2. It enables effective human-computer interaction: by mouse dragging the "focus", the user can navigate in the data without loosing the context. In H2 the "fish-eye" behavior originates not simply by a non-linear view transformation but rather by extraordinary, non-Euclidean properties of the H2. Especially, the exponential growth of length and area of the underlying space makes the H2 a prime target for mapping hierarchical and (now also) high-dimensional data.Several high-dimensional mapping examples including synthetic and real-world data are presented. Since high-dimensional data produce "ring"-shaped displays, we present methods to enhance the display by modulating the dissimilarity contrast. This is demonstrated for an application for unstructured text: i.e., by using multiple film critiques from news:rec.art.movies.reviews and www.imdb.com, each movie is placed within the H2--creating a "space of movies" for interactive exploration. This paper considers the problem of embedding trees into the hyperbolic plane. We show that any tree can be realized as the Delaunay graph of its embedded vertices. Particularly, a weighted tree can be embedded such that the weight on each edge is realized as the hyperbolic distance between its embedded vertices. Thus the embedding preserves the metric information of the tree along with its topology. The distance distortion between non adjacent vertices can be made arbitrarily small --- less than a (1+e) factor for any given e. Existing results on low distortion of embedding discrete metrics into trees carry over to hyperbolic metric through this result. The Delaunay character implies useful properties such as guaranteed greedy routing and realization as minimum spanning trees.