Hyperbolic Graph Convolutional Neural Networks

By Ines Chami, Rex Ying, Christopher R'e, Jure Leskovec. Neural Information Processing Systems, 2019

888 citations recorded by the source corpus.

Graph convolutional neural networks (GCNs) embed nodes in a graph into Euclidean space, which has been shown to incur a large distortion when embedding real-world graphs with scale-free or hierarchical structure. Hyperbolic geometry offers an exciting alternative, as it enables embeddings with much smaller distortion. However, extending GCNs to hyperbolic geometry presents several unique challenges because it is not clear how to define neural network operations, such as feature transformation and aggregation, in hyperbolic space. Furthermore, since input features are often Euclidean, it is unclear how to transform the features into hyperbolic embeddings with the right amount of curvature. Here we propose Hyperbolic Graph Convolutional Neural Network (HGCN), the first inductive hyperbolic GCN that leverages both the expressiveness of GCNs and hyperbolic geometry to learn inductive node representations for hierarchical and scale-free graphs. We derive GCNs operations in the hyperboloid model of hyperbolic space and map Euclidean input features to embeddings in hyperbolic spaces with different trainable curvature at each layer. Experiments demonstrate that HGCN learns embeddings that preserve hierarchical structure, and leads to improved performance when compared to Euclidean analogs, even with very low dimensional embeddings: compared to state-of-the-art GCNs, HGCN achieves an error reduction of up to 63.1% in ROC AUC for link prediction and of up to 47.5% in F1 score for node classification, also improving state-of-the art on the Pubmed dataset.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/97ebd482a78e6e6c1ba51da5e1b2f8e7640cc8b5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “…al., 2018), novel techniques for pooling node representations in order perform graph classiﬁcation, e.g., (Cangea et al., 2018; Gao & Ji, 2019; Ying et al., 2018; Zhang et al., 2018), incorporating distance information (You et al., 2019), and non-euclidian geometry approaches (Chami et al., 2019).”
Differentiating through the Fréchet Mean (2020, methodology): “In the first setting, we directly modify the hyperbolic aggregation strategy in Hyperbolic GCNs (Chami et al., 2019) to use our differentiable Fréchet mean layer.”
Artificial Neural Networks and Machine Learning – ICANN 2021: 30th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 14–17, 2021, Proceedings, Part III (2021, background): “The works [29,6] have empirically shown that the hyperbolic setting is better suited for representation learning on real-world graphs with scale-free or hierarchical structure.”
Suicide Ideation Detection via Social and Temporal User Representations using Hyperbolic Learning (2021, methodology): “Next, we perform a linear transformation to capture macroscopic neighborhood structures on the Poincaré ball manifold, followed by a Frechet Mean operation (Fréchet, 1948) denoted by FM. Owing to the trainable curvatureK, Hyper-SOS utilizes a hyperbolic non-linear activation with varying curvature (”
A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources (2020, positive): “Some attempts have been made towards hyperbolic HG embedding, and the results are rather promising [62], [121], [122].”
Hyperbolic Graph Neural Networks (2019, background): “[10] also proposed an extension of graph neural networks to hyperbolic geometry.”
AM-GCN: Adaptive Multi-channel Graph Convolutional Networks (2020, background): “5 RELATEDWORK Recently, graph convolutional network (GCN) models [4, 9, 17, 23, 33, 35] have been widely studied.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “Hyperbolic Graph Convolutional Neural Networks Hyperbolic Graph Convolution Networks (HGCN) [22] and Hyperbolic Graph Neural Networks (HGNN) [75] apply graph convolutions in hyperbolic space by leveraging the Euclidean tangent space, which provides a first-order approximation of the hyperbolic manif”
Low-Dimensional Hyperbolic Knowledge Graph Embeddings (2020, methodology): “…tail entity: where Since optimization in hyperbolic space is practically challenging, we instead deﬁne all parameters in the tangent space at the origin, optimize embed-dings using standard Euclidean techniques, and use the exponential map to recover the hyperbolic parameters (Chami et al., 2019).”
Understanding over-squashing and bottlenecks on graphs via curvature (2021, background): “It offers an appealing framework to study the properties of graphs, in particular arguing that graphs, like manifolds, exhibit curvature that makes them more suitable to be realized in spaces with hyperbolic geometry (Liu et al., 2019; Chami et al., 2019; Boguna et al., 2021).”
HypRAG: Hyperbolic Dense Retrieval for Retrieval Augmented Generation (2026, unknown): “However, this approach provably contracts representations toward the origin (Ganea et al., 2018a; Chami et al., 2019), destroying hierarchical structure encoded in radial depth.”