Source-linked AI summary
Neural Embeddings of Graphs in Hyperbolic Space
Benjamin Paul Chamberlain, James Clough, Marc Peter Deisenroth
TL;DR
Existing graph and language embeddings generally use Euclidean spaces, although complex networks can have hyperbolic structure that Euclidean geometry does not naturally represent. The paper introduces neural graph embeddings with hyperbolic backpropagation and finds that hyperbolic embeddings significantly outperform Euclidean or DeepWalk embeddings on vertex-classification tasks across multiple real-world networks.
Problem
Previous neural embedding models assumed Euclidean geometry, despite evidence that complex networks exhibit hyperbolic structure with hierarchy, clustering, and power-law degree distributions.
Method
The paper adapts the Skipgram-based graph-embedding approach and formulates backpropagation for neural embeddings in hyperbolic space.
Results
Hyperbolic space embeddings significantly outperform Euclidean embeddings for classifying vertices of complex networks across multiple networks.
Takeaways & Limitations
Embedding complex networks in their natural hyperbolic geometry improves downstream vertex-classification performance on the evaluated datasets.
Abstract
from arXiv · showhide
Neural embeddings have been used with great success in Natural Language Processing (NLP). 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 have been learned in high-dimensional Euclidean spaces. However, recent work has shown that the appropriate isometric space for embedding complex networks is not the flat Euclidean space, but 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 embedding graphs in their natural geometry significantly improves performance on downstream tasks for several real-world public datasets.
1 INTRODUCTION
Embedding methods represent complex data in compact continuous spaces where distances encode similarity, and neural embeddings extend this approach to unlabeled downstream tasks. This paper introduces hyperbolic neural embeddings for graphs, motivated by the non-Euclidean geometry of complex networks.
- Embedding methods: Embedding methods reduce high-dimensional complex data to continuous spaces whose distances measure similarity.They provide compact representations that encapsulate similarity and improve machine-learning inputs compared with sparse schemes.
- Neural embeddings: Neural embeddings learn vector representations as network weights through backpropagation and support many unlabeled downstream tasks.Examples include missing-edge prediction, vertex attribution, recommendations, and categorisation.
- Motivation: Complex networks such as the Internet and academic citations can exhibit an underlying hyperbolic geometry rather than Euclidean structure.Hyperbolic geometry provides a continuous analogue of tree-like graphs, while network properties such as power-law degrees, clustering, and hierarchy emerge naturally in embedded random graphs.
- Graph embeddings: Graph embedding methods extend word-based Skipgram by generating vertex sequences with random walks and treating vertices analogously to words.DeepWalk introduced this formulation, followed by variations in LINE and Node2vec.
- Contribution: The paper introduces neural embeddings in hyperbolic space, formulates hyperbolic backpropagation, and evaluates them on vertex classification across multiple networks.The stated contribution is to use the natural geometry of complex networks for graph embeddings.
2 HYPERBOLIC GEOMETRY
Hyperbolic geometry differs from Euclidean geometry through negative curvature, exponential spatial growth, and multiple parallels through a point. The Poincaré disk represents this space compactly while preserving angles and encoding distances that expand toward its boundary.
- Hyperbolic geometry: Hyperbolic space has uniform negative curvature and permits infinitely many lines through one point parallel to a given line.Euclidean space is flat, while elliptic space has positive curvature.
- Hyperbolic geometry: Figure 1 illustrates hyperbolic properties using constant-area tiles and families of parallel lines.The two panels correspond to spatial area distortion and the parallel-postulate difference.
- Hyperbolic geometry: Circle area and sphere volume grow exponentially with radius in hyperbolic space rather than polynomially as in Euclidean space.This motivates using low-dimensional hyperbolic spaces to represent structures that low-dimensional Euclidean spaces may not capture effectively.
- Poincaré Disk Model: The Poincaré disk models the infinite hyperbolic plane inside a finite unit disk and generalizes to a d-dimensional Poincaré ball.The paper works with the two-dimensional disk.
- Poincaré Disk Model: In the Poincaré disk, hyperbolic distances grow exponentially toward the boundary, which represents infinitely distant points.Tiles retain constant hyperbolic area while shrinking in Euclidean appearance, and geodesics appear as orthogonal arcs or diameters.
- Poincaré Disk Model: Vertices near the disk center can have many close neighbours, while vertices near the edge can remain far apart.This geometric arrangement supplies the intuition for representing complex-network connectivity in the disk.
- Poincaré Disk Model: The model uses polar coordinates and a hyperbolic inner product to define similarities and distances.The origin distance is rh = 2 arctanh re, and a circle of hyperbolic radius R has circumference C = 2π sinh R.
3 NEURAL EMBEDDING IN HYPERBOLIC SPACE
The model replaces Skipgram’s Euclidean vector spaces and dot products with Poincaré disks and hyperbolic inner products, learning graph embeddings through prediction and backpropagation.
- Model formulation: Skipgram updates output vectors toward observed input-context pairs and away from other vectors, with changes proportional to prediction error.The model applies analogous, more complicated updates to input vectors.
- Model formulation: Graph embeddings replace Skipgram’s two Euclidean vector spaces with two Poincaré disks and predict output/context vertices from an input vertex.The predictive objective is optimized using a softmax-based conditional distribution.
- Model formulation: Hyperbolic inner products replace the Euclidean dot products used in Skipgram.The conditional predictive distribution is formed with a softmax function.
- Negative sampling: Negative sampling replaces the computationally demanding full softmax denominator with sampled noise contrasts and is used because it is faster.The negative log likelihood separates the observed output from sampled negative vertices.
- Model learning: Backpropagation is performed in natural polar hyperbolic coordinates before vectors are mapped back to Euclidean coordinates on the Poincaré disk.The coordinates use radius and angle, but the system addresses a singularity at the origin by initializing vectors in a restricted patch.
4 EXPERIMENTAL EVALUATION
The evaluation compares hyperbolic embeddings with Euclidean DeepWalk embeddings on five public networks, using vertex attribution and visualization experiments. Hyperbolic embeddings capture community structure and significantly outperform DeepWalk across datasets.
- Datasets: The evaluation covers five publicly available network datasets for vertex attribution.The datasets are Karate, Polbooks, Football, Adjnoun, and Polblogs.
- Visualizing embeddings: In the Zachary karate network, the two factions are linearly separable in 2D hyperbolic space but not in the Euclidean embedding.Both embeddings use five epochs on the same random walks.
- Experimental setup: Embeddings are generated from ten-step random walks originating at each vertex and compared across hyperbolic and Euclidean DeepWalk spaces.The experiments compare DeepWalk dimensions from 2D through 128D; models use the same random-walk data and training parameters.
- Vertex attribute prediction: Macro F1 scores are evaluated against the percentage of labelled vertices used to train a logistic regression classifier.Error bars represent one standard error from ten repetitions.
5 CONCLUSION
The paper introduces neural embeddings in hyperbolic space as an alternative to the previously assumed flat Euclidean geometry. It argues that hyperbolic structure suits complex networks and reports superior vertex-classification performance.
- Contribution: The paper introduces neural embeddings in hyperbolic space, whereas previous embedding models assumed flat Euclidean geometry.This extends neural embedding methods beyond the Euclidean setting.
- Motivation: Hyperbolic space naturally supports power-law degree distributions, strong clustering, and hierarchical community structure in embedded random graphs.These properties motivate using hyperbolic geometry for complex-network embeddings.
- Result: Hyperbolic-space embeddings significantly outperform Euclidean embeddings on vertex classification tasks for complex networks.The conclusion summarizes the demonstrated performance difference across the evaluated task setting.
(a) College football
Figure 5 plots macro F1 against the percentage of labelled vertices used for training in the college-football subfigure. Hyperbolic embeddings are compared with Euclidean DeepWalk embeddings across dimensions.
- (a) College football: Macro F1 score is shown on the y-axis against the percentage of labelled vertices used for training on the x-axis.Blue denotes hyperbolic embeddings and red denotes Euclidean DeepWalk embeddings.
- (a) College football: Hyperbolic embeddings significantly outperform Euclidean DeepWalk embeddings in the plotted comparison.Error bars show standard error from the mean over ten repetitions.
- (a) College football: The figure compares a 2D hyperbolic embedding with DeepWalk architectures whose embeddings range from 2D to 128D.The caption describes this as a consistent trend across the datasets.