text: 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.
  @cite_7: Recent years have shown a promising progress in understanding geometric underpinnings behind the structure, function, and dynamics of many complex networks in nature and society. However, these promises cannot be readily fulfilled and lead to important practical applications, without a simple, reliable, and fast network mapping method to infer the latent geometric coordinates of nodes in a real network. Here, we present HyperMap, a simple method to map a given real network to its hyperbolic space. The method utilizes a recent geometric theory of complex networks modeled as random geometric graphs in hyperbolic spaces. The method replays the network's geometric growth, estimating at each time-step the hyperbolic coordinates of new nodes in a growing network by maximizing the likelihood of the network snapshot in the model. We apply HyperMap to the Autonomous Systems (AS) Internet and find that: 1) the method produces meaningful results, identifying soft communities of ASs belonging to the same geographic region; 2) the method has a remarkable predictive power: Using the resulting map, we can predict missing links in the Internet with high precision, outperforming popular existing methods; and 3) the resulting map is highly navigable, meaning that a vast majority of greedy geometric routing paths are successful and low-stretch. Even though the method is not without limitations, and is open for improvement, it occupies a unique attractive position in the space of tradeoffs between simplicity, accuracy, and computational complexity.
  @cite_21: The Popularity-Similarity (PS) model sustains that clustering and hierarchy, properties common to most networks representing complex systems, are the result of an optimisation process in which nodes seek to form ties, not only with the most connected (popular) system components, but also with those that are similar to them. This model has a geometric interpretation in hyperbolic space, where distances between nodes abstract popularity-similarity trade-offs and the formation of scale-free and strongly clustered networks can be accurately described.
  @cite_10: The different factors involved in the growth process of complex networks imprint valuable information in their observable topologies. How to exploit this information to accurately predict structural network changes is the subject of active research. A recent model of network growth sustains that the emergence of properties common to most complex systems is the result of certain trade-offs between node birth-time and similarity. This model has a geometric interpretation in hyperbolic space, where distances between nodes abstract this optimisation process. Current methods for network hyperbolic embedding search for node coordinates that maximise the likelihood that the network was produced by the afore-mentioned model. Here, a different strategy is followed in the form of the Laplacian-based Network Embedding, a simple yet accurate, efficient and data driven manifold learning approach, which allows for the quick geometric analysis of big networks. Comparisons against existing embedding and prediction techniques highlight its applicability to network evolution and link prediction.
  @cite_12: A framework is developed in which new connections to a growing network optimize geometric trade-offs between popularity and similarity, instead of simply preferring popular nodes; this approach accurately describes the large-scale evolution of various networks.
  @cite_11: Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term “angular coalescence.” Based on this phenomenon, we propose a class of algorithms that offers fast and accurate “coalescent embedding” in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science. Mapping complex networks to underlying geometric spaces can help understand the structure of networked systems. Here the authors propose a class of machine learning algorithms for efficient embedding of large real networks to the hyperbolic space, with potential impact on big network data analysis.
summary: Many hyperbolic embedding algorithms are based on two-dimensional hyperbolic disk, which was popularised by the Popularity-Similarity (or PS) model @cite_12 . In @cite_12 , Maximum Likelihood (ML) was used in to search the space of all PS models with similar structural properties as the observed network, to find the one that fit it best. This was extended by the authors in @cite_7 . Due to the computationally demanding task of maximum likelihood estimation, often heuristic methods are used. For example, @cite_10 used Laplacian Eigenmaps to estimate the angular coordinates of nodes in the PS model. The authors then combined both approaches to leverage the performance of ML estimation against the efficiency of heuristic search with a user controlled parameter in @cite_21 . Additionally, @cite_11 propose the use of classical manifold learning techniques in the PS model setting with a framework that they call .