Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding

Alessandro Muscoloni, Carlo Vittorio CannistraciarXiv 2019 · arXiv

Introduction

In the analysis of complex networks—ranging from social interactions to protein-protein signaling—researchers frequently utilize geometric embeddings to represent high-dimensional data in lower-dimensional spaces. Hyperbolic space has emerged as a preferred geometry for these embeddings because its inherent curvature effectively captures the hierarchical and tree-like structures common in real-world systems. In such models, a node's radial position typically indicates its hierarchical importance, while its angular position reflects its similarity to other nodes.

Ideally, nodes belonging to the same community should cluster within a narrow angular range. However, the evaluation of this "angular separation" has historically been qualitative, relying on visual inspection of plots. This paper addresses this limitation by introducing the Angular Separation Index (ASI), a rigorous quantitative metric designed to measure community segregation in geometric embeddings.

The Angular Separation Index (ASI)

The ASI provides a mathematical framework to quantify how well-defined community boundaries are within an embedding. The logic of the index is structured around three primary steps:

  1. Boundary Definition: For any given community, the metric identifies the angular "extremes" (the minimum and maximum angles) that encompass all its members.
  2. Error Quantification: The metric counts the number of "mistakes"—nodes from external communities that fall within the angular boundaries of the community being evaluated.
  3. Normalization: The total count of mistakes is normalized against a "worst-case scenario" null model, where node positions are entirely randomized.

The resulting index ranges from 0 to 1, where 0 represents random mixing (no separation) and 1 represents perfect angular segregation.

Dimensionality: 2D vs. 3D

The authors developed versions of ASI for both 2D embeddings (where nodes are placed on a circle) and 3D embeddings (where nodes are placed on a sphere). In the 3D implementation, the community's territory is defined by a convex hull on the sphere's surface. To ensure the robustness of the metric, the framework includes a statistical p-value test to confirm that observed separation is not the result of random chance.

Key Insights: The Dimensionality Jump

One of the most significant findings of this research is the discovery of a "dimensionality jump" related to network temperature ($T$). In hyperbolic models, temperature dictates the balance between similarity-based connections and random long-range links.

The study found that as temperature increases in a network generated in 2D, the 2D embedding's ability to separate communities degrades significantly. However, when these same networks are embedded in 3D hyperbolic space, high angular separation is maintained. This suggests that random long-range links effectively act as "dimensional tunnels," increasing the intrinsic dimensionality of the network and requiring higher-dimensional geometric spaces to accurately represent its structure.

Experimental Validation and Benchmarking

The ASI was validated using a combination of synthetic and real-world datasets:

  • Synthetic Data: Using the nonuniform Popularity-Similarity Optimization (nPSO) model, the researchers generated networks with controlled levels of clustering and mixing. ASI accurately tracked the degradation of community structure as temperature increased, proving its sensitivity as a diagnostic tool.
  • Real-World Benchmarks: The metric was applied to eight classic networks, including Zachary’s Karate Club, the Football network, and various intra-organizational social networks (Opsahl 8-11).

Algorithm Performance

ASI allowed for an objective ranking of state-of-the-art embedding algorithms. The results indicated that Coalescent Embedding variants generally outperform other methods. Specifically, the RA2-ncISO variant achieved a mean ASI of 0.78 in 2D benchmarks, significantly higher than the 0.60 achieved by HyperMap-CN. Furthermore, the study demonstrated that 3D embeddings consistently yield higher ASI scores than 2D; for instance, the opsahl_10 network improved from an ASI of 0.91 in 2D to a perfect 1.0 in 3D.

Conclusion and Limitations

The Angular Separation Index offers a general, geometry-agnostic tool for evaluating data clusters. While tested extensively in hyperbolic space, it is equally applicable to Euclidean or other geometric embeddings.

Despite its utility, the authors note certain limitations. The 3D version is more computationally intensive than the 2D version due to the reliance on random reshuffling for normalization. Additionally, the 3D method's reliance on convex hulls assumes that communities occupy a contiguous, convex area on the sphere; fragmented or concave communities may result in an over-counting of "mistakes." Future work will involve extending the ASI framework to dimensions higher than 3D and optimizing the computational efficiency for massive datasets.

Summary updated

Abstract

Analysis of 'big data' characterized by high-dimensionality such as word vectors and complex networks requires often their representation in a geometrical space by embedding. Recent developments in machine learning and network geometry have pointed out the hyperbolic space as a useful framework for the representation of this data derived by real complex physical systems. In the hyperbolic space, the radial coordinate of the nodes characterizes their hierarchy, whereas the angular distance between them represents their similarity. Several studies have highlighted the relationship between the angular coordinates of the nodes embedded in the hyperbolic space and the community metadata available. However, such analyses have been often limited to a visual or qualitative assessment. Here, we introduce the angular separation index (ASI), to quantitatively evaluate the separation of node network communities or data clusters over the angular coordinates of a geometrical space. ASI is particularly useful in the hyperbolic space - where it is extensively tested along this study - but can be used in general for any assessment of angular separation regardless of the adopted geometry. ASI is proposed together with an exact test statistic based on a uniformly random null model to assess the statistical significance of the separation. We show that ASI allows to discover two significant phenomena in network geometry. The first is that the increase of temperature in 2D hyperbolic network generative models, not only reduces the network clustering but also induces a 'dimensionality jump' of the network to dimensions higher than two. The second is that ASI can be successfully applied to detect the intrinsic dimensionality of network structures that grow in a hidden geometrical space.
BibTeX
@misc{muscoloni2019angular,
  author = {Alessandro Muscoloni and Carlo Vittorio Cannistraci},
  title = {{Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding}},
  year = {2019},
  eprint = {1907.00025},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.00025},
}
Figure