Mapping Networks to Hyperbolic Space: Seeing the Whole Picture

Hey there! Ever look at a complex network – maybe a social network, a biological system, or even the internet – and wish you could just *see* its structure, its hidden geometry? Well, that’s where network embedding comes in. It’s like taking that tangled mess and giving each piece (each node or vertex) a coordinate in some kind of space. And for many real-world networks, it turns out that *hyperbolic space* is a pretty neat place to put them.

Why hyperbolic space, you ask? Think of it as a space that expands really fast, unlike flat Euclidean space (like a sheet of paper) or spherical space (like a ball). This rapid expansion is surprisingly good at mimicking the way many real networks grow and connect. It naturally leads to properties we see everywhere: lots of nodes with only a few connections and a few “hubs” with tons (a heavy-tailed degree distribution), tight-knit communities (high clustering), and even hierarchical structures. Plus, embedding networks in hyperbolic space can even help us find efficient paths through them, like for routing information.

People have spent a lot of time figuring out how to place network nodes into this hyperbolic space. The usual way involves finding the single “best” spot for each node, often by maximizing some function or minimizing some error. And these methods are great for giving us *a* picture of the network. But here’s the catch…

The Problem: Missing Uncertainty and Multiple Realities

Most existing methods give you just *one* set of coordinates, one single embedding. It’s like taking a single photograph of a dynamic scene and saying, “This is exactly how it is.” But what if there’s a bit of fuzziness? What if the data isn’t perfectly clear? What if there’s a range of slightly different, yet equally plausible, ways the network could be structured in that space?

This is the big blind spot: these methods largely ignore *uncertainty*. They don’t give you error bars on where a node is placed, or how confident you should be about the properties you calculate from that embedding. And even more intriguing, they can easily miss something called *multimodality*. This means a network might actually have *two or more* fundamentally different, yet equally valid, embeddings in hyperbolic space. An algorithm that only looks for the single “best” solution will just pick one and pretend the others don’t exist. That feels like we’re missing part of the story, right?

Enter BIGUE: A Bayesian Approach

So, how do we get the full story? We need to move beyond finding just one point and instead explore the *distribution* of all possible embeddings that are compatible with the network data. This is where Bayesian methods shine. Instead of a single estimate, they give us a probability distribution over the possibilities.

Our proposed algorithm, which we’ve charmingly named BIGUE (Bayesian Inference of a Graph’s Unknown Embedding), does just that. It uses a technique called Markov Chain Monte Carlo (MCMC) sampling. Think of MCMC as a smart way to wander around the space of possible embeddings, spending more time in the regions that are more probable given the network data. By collecting lots of these “samples,” we can build up a picture of the entire probability landscape.

We work within a specific model called the S¹ model, which is closely related to the standard hyperbolic plane model. This model defines the probability of an edge existing between two nodes based on their positions (angular coordinates), their “popularity” or degree-like parameter, and a parameter controlling clustering. BIGUE samples from the *posterior distribution* – that’s the probability distribution of the embedding parameters *given* the observed network.

The Challenge: Navigating Complex Possibilities

Sounds straightforward, right? Just run an MCMC sampler! Well, not so fast. It turns out the space of possible embeddings for a network in hyperbolic space is incredibly complex. Imagine a landscape with lots of steep hills, deep valleys, and separate peaks. Standard MCMC algorithms, like a simple random walk or even more sophisticated gradient-based methods (like Hamiltonian Monte Carlo, or HMC), really struggle to explore this kind of terrain properly.

Why is it so tricky? One reason is symmetry. The S¹ model has symmetries related to rotations and reflections, meaning infinite embeddings are technically equivalent. We handle some of this by fixing a couple of high-degree nodes, but the landscape is still bumpy. Another big issue comes from the structure of the network itself. If two nodes aren’t connected, the model predicts they should be far apart. If the sampler tries to move them close together, the probability (and thus the posterior density) drops dramatically, creating these “barriers” in the landscape. For sparse, large networks, these barriers are everywhere! Standard samplers get stuck in local regions and don’t explore the whole space of possibilities. They show poor “mixing,” meaning the samples they collect aren’t truly representative of the whole distribution.

The Solution: Cluster Transformations to the Rescue

To overcome these challenges, we got a bit clever. We noticed that in hyperbolic space, nodes that are far apart are essentially independent. This hints that we can perhaps move groups of nodes around together. This idea led us to incorporate “cluster-based transformations” into our MCMC algorithm.

First, we group vertices into clusters based on their current angular positions. Then, we apply one of three transformations to randomly selected clusters:

• Flip: Reflecting a cluster’s positions.
• Exchange: Swapping the relative positions of two clusters.
• Translate: Moving one cluster to the relative position of another.

These transformations help the sampler make big jumps across the complex landscape, effectively stepping over those tricky barriers and exploring different regions (including those representing alternative embeddings). We combine these cluster transformations (CT) with a basic random walk (RW) for fine-tuning – that’s BIGUE (RW+CT).

We found that adding these cluster transformations drastically improves the mixing of the MCMC algorithm. It explores the posterior distribution much more efficiently than a simple random walk or even the sophisticated HMC, which struggles with the non-smooth landscape. While our current implementation of BIGUE is still a bit slow for very large networks (scaling beyond a few hundred nodes is tough right now), the cluster transformations make it significantly more effective than other MCMC approaches we tested. Plus, our results confirm that the posterior distributions aren’t simple shapes like Gaussian (normal) distributions, proving that these more complex sampling methods like BIGUE are necessary to get an accurate picture.

What BIGUE Shows Us: Beyond a Single Answer

Having a reliable way to sample from the posterior distribution is powerful. It means we don’t just get a single point estimate; we get a *range* of plausible embeddings. This allows us to quantify uncertainty using *credible intervals* – essentially, Bayesian error bars – on the coordinates of the nodes and on the properties we calculate from the embedding.

When we compared BIGUE’s results to Mercator (a popular maximum likelihood method), we found that Mercator’s single estimate often falls within BIGUE’s credible intervals. This is good – it means Mercator isn’t usually *wrong*, but it’s only giving you *one* point in a whole cloud of possibilities. BIGUE shows you the whole cloud.

For example, we can calculate the greedy routing success rate (how well you can navigate the network using the hyperbolic coordinates as addresses). Mercator gives one value. BIGUE gives a *distribution* of values, showing that while some plausible embeddings are as navigable as Mercator’s, many others are less reliable. Similarly, for properties like the global hierarchy level, BIGUE often suggests that networks might be *less* hierarchical than a single estimate implies, because it averages over many possibilities.

Crucially, BIGUE can reveal multimodality. We showed that even a simple synthetic network can have two distinct, equally valid embeddings. Standard optimization methods would likely just find one. BIGUE, by exploring the posterior, can show you that both possibilities exist. This isn’t just a theoretical curiosity; it means the network structure might be ambiguous in interesting ways. And as we saw, the posterior distributions are definitely *not* simple Gaussian shapes – they can be skewed, have multiple peaks, and complex correlations, reinforcing why MCMC is needed.

We also tested BIGUE on several real-world networks. It reproduced basic properties like density and clustering just as well as Mercator, but with the added benefit of showing the uncertainty. While it struggled with a couple of networks where the S¹ model might not be a great fit overall, for most, it provided valuable insights into the range of plausible embeddings and the properties derived from them.

Looking Ahead: Making it Faster and Better

While BIGUE is a significant step forward in quantifying uncertainty and revealing multimodality, its main limitation right now is its computational cost. Sampling from these complex distributions is slow, and scaling to networks with thousands or millions of nodes is a major challenge for future work.

There are exciting avenues to explore for speedups. We could try generalizing the cluster transformations to higher-dimensional hyperbolic spaces, which might make it easier for the sampler to navigate around those tricky barriers. We could also look at integrating more efficient gradient-based methods like HMC in a smarter way, perhaps within the cluster framework. Approximating parts of the calculation (like the likelihood) or exploiting network symmetries could also help.

Beyond just sampling, the success of the cluster transformations suggests they might even be useful for improving existing maximization algorithms like Mercator, helping them find better single solutions or perhaps even revealing multiple maxima.

Ultimately, BIGUE gives us a more complete picture of network structure in hyperbolic space. By quantifying uncertainty and revealing alternative embeddings, it moves us beyond a single snapshot to a richer, more nuanced understanding of how complex networks are organized.

Source: Springer