Source-linked AI summary
Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
Josephine Maria Thomas, Alessandro Muscoloni, Sara Ciucci, Ginestra Bianconi, Carlo Vittorio Cannistraci
TL;DR
The paper addresses how to compute network embeddings when an unweighted adjacency matrix lacks a norm revealing hidden connectivity geometry. It proposes manifold-based methods, including ncISO and MCE/ncMCE, and reports that pre-weighting boosts MCE/ncMCE performance, while manifold-based representations have limited compression power.
Problem
An unweighted adjacency matrix does not provide a norm that reveals the hidden connectivity geometry needed to compute its minimum spanning tree.
Method
The paper develops manifold-based embedding methods, including ncISO without kernel centering and minimum curvilinear embedding approaches for network data.
Results
Pre-weighting significantly boosts MCE/ncMCE performance, with results reported across seven real social interaction networks.
Takeaways & Limitations
Providing a proximity graph is an important advantage for the embedding approach because the graph is already available.
Takeaways & Limitations
Manifold-based techniques offer less compression power because their representations use two orthogonal dimensions.
Abstract
from arXiv · showhide
Complex network topologies and hyperbolic geometry seem specularly connected, and one of the most fascinating and challenging problems of recent complex network theory is to map a given network to its hyperbolic space. The Popularity Similarity Optimization (PSO) model represents - at the moment - the climax of this theory. It suggests that the trade-off between node popularity and similarity is a mechanism to explain how complex network topologies emerge - as discrete samples - from the continuous world of hyperbolic geometry. The hyperbolic space seems appropriate to represent real complex networks. In fact, it preserves many of their fundamental topological properties, and can be exploited for real applications such as, among others, link prediction and community detection. Here, we observe for the first time that a topological-based machine learning class of algorithms - for nonlinear unsupervised dimensionality reduction - can directly approximate the network's node angular coordinates of the hyperbolic model into a two-dimensional space, according to a similar topological organization that we named angular coalescence. On the basis of this phenomenon, we propose a new class of algorithms that offers fast and accurate coalescent embedding of networks in the hyperbolic space even for graphs with thousands of nodes.
Methods
The PSO model generates networks on a hyperbolic plane by balancing node popularity and similarity. New nodes receive radial and angular coordinates, connect probabilistically, and the process continues until the target size is reached.
- New nodes are assigned radial coordinates based on arrival time and uniformly sampled angular coordinates.
- The model uses four parameters controlling average degree, degree-distribution exponent, clustering, and hyperbolic-plane curvature.
- Existing nodes move radially outward according to popularity fading as the network grows.
- Connections form probabilistically from hyperbolic distances until each new node reaches its target degree, after which growth stops at the specified network size.
- PSO networks optimize a trade-off between node popularity, represented radially, and similarity, represented angularly.
HyperMap
HyperMap reconstructs a network’s hyperbolic coordinates by replaying its inferred growth sequence. It orders nodes by degree, assigns radial coordinates, and estimates angular coordinates through likelihood maximization.
- HyperMap maps networks into hyperbolic space by replaying their growth process and recovering polar coordinates for added nodes.
- For curvature −1, the first node receives radial coordinate 0 and a random angular coordinate, while later nodes receive time-based radial coordinates.
- Each node’s angular coordinate is selected by maximizing the likelihood that the observed network was generated by the E-PSO model.
- The angular search tests coordinates in increments of 2π/N and chooses the coordinate producing the highest likelihood.
- Nodes are sorted by decreasing degree because higher-degree nodes are inferred to have appeared earlier.
Manifold-based embedding
The paper applies manifold-based dimensionality-reduction methods directly to network topology, where the proximity graph is already available. ISO uses shortest-path kernels, whereas LE decomposes the network Laplacian without requiring kernel inference.
- Isomap and Laplacian Eigenmaps are used as manifold-based methods for nonlinear dimensionality reduction of networks.
- Unlike classical manifold learning, the network itself supplies the proximity graph, avoiding a difficult graph-inference step.
- ISO extracts shortest-path distances, centers the resulting kernel, and applies SVD for two-dimensional node embedding.
- The noncentered ISO variant, ncISO, omits kernel centering before embedding.
- LE is faster than ISO because it does not require inferring a distance kernel from network structure.
- LE embeds nodes using eigenvectors associated with the second and third smallest Laplacian eigenvalues, omitting the zero-eigenvalue eigenvector.
Minumum Curvilinearity and Minimum curvilinear embedding
Minimum Curvilinearity methods use a minimum spanning tree to learn nonlinear node similarities and produce hierarchical embeddings. Pre-weighting the network links improves their performance, while standard manifold methods have compression limitations.
- Minimum Curvilinearity and Minimum curvilinear embedding: MCE and ncMCE compress network information into one dimension by linearizing hidden nonlinear patterns.
- Minimum Curvilinearity and Minimum curvilinear embedding: Manifold-based methods offer less compression because they require two orthogonal representation dimensions.
- Minimum Curvilinearity and Minimum curvilinear embedding: Minimum Curvilinearity methods learn nonlinear similarities through a minimum spanning tree and embed the resulting kernel with SVD.
- Minimum Curvilinearity and Minimum curvilinear embedding: MCE generally linearizes patterns along the first embedding dimension, whereas ncMCE does so along the second.
- Minimum Curvilinearity and Minimum curvilinear embedding: MCE and ncMCE are presented as hierarchical embedding methods that use the MST to navigate different network regions.
- Minimum Curvilinearity and Minimum curvilinear embedding: The MST uses only N−1 links, allowing these methods to exploit a small fraction of the network connections.
- Minimum Curvilinearity and Minimum curvilinear embedding: Pre-weighting links provides a topological mapping strategy and significantly boosts MCE/ncMCE performance.
Real network datasets
Information on the real networks used for link-prediction evaluation is provided in the supplementary information.
- The supplementary information describes the real networks used in the link-prediction evaluation.
- These networks are used to assess embedding methods on real-world link-prediction data.
- The dataset information accompanies the evaluation of methods on real networks.
Hardware and software details
The methods and simulations used MATLAB on a Dell workstation running Windows 7 Professional with substantial memory and two Intel Xeon processors.
- MATLAB code was used for all methods and simulations.
- The experiments ran on a Dell workstation under Windows 7 Professional with 192 GB of RAM.
- The workstation used two Intel Xeon X5550 processors clocked at 2.66 and 2.67 GHz.
Funding
The work received support from a Technische Universität Dresden independent group leader starting grant, its Centre for High Performance Computing, and an Erasmus+ traineeship programme.
- The work was mainly supported by an independent group leader starting grant from Technische Universität Dresden.
- The Centre for Information Services and High Performance Computing of Technische Universität Dresden also provided support.
- AM received partial support from the Erasmus+ Mobility for traineeships programme of the University of ...
Figures
The figures illustrate coalescent embedding, its adjustment steps, synthetic-network evaluation, computational comparisons, and real-network link-prediction evaluation.
- Fig. 1: Isomap maps an unweighted adjacency matrix into a circular pattern following the PSO model’s angular coordinates.
- Fig. 2: The coalescent-embedding algorithm adjusts nodes on a circumference while preserving angular coordinates or ordering.
- Fig. 3: Synthetic-network performance is measured by Pearson correlation between original and reconstructed pairwise hyperbolic distances.
- Fig. 3: Equidistant adjustment improves performance when low temperatures and m=2 make RA-LE without adjustment perform poorly.
- Fig. 4: Coalescent approaches embed 1000-node networks in generally less than 10 seconds, whereas Hypermap takes approximately 6 hours.
- Table 1: The real-network table evaluates link prediction by removing 10% of links, repeating trials 500 times, and reporting mean precision relative to a random predictor.
Suppl. Fig. 2. Evaluation on synthetic networks: LE methods
The figure evaluates all LE-based dimensionality-reduction methods on synthetic networks using correlations between original and reconstructed hyperbolic distances.
- The figure reports performance for all methods using LE for dimensionality reduction.
- LE methods are evaluated by comparing pairwise hyperbolic distances in the original PSO model with those in reconstructed space.The evaluation metric is Pearson correlation between the two sets of distances.
- Reported performance is the average correlation across 100 synthetic networks for each parameter combination.
Suppl. Fig. 3. Evaluation on synthetic networks: ISO methods
The supplementary evaluation reports synthetic-network performance for ISO, ncISO, MCE, and ncMCE methods, alongside examples illustrating how temperature changes network structure.
- Method evaluations: Performance is reported for all methods using ISO, ncISO, MCE, and ncMCE for dimensionality reduction.
- Evaluation metric: The ISO, ncISO, MCE, and ncMCE evaluations use the performance definition described in Suppl. Fig. 2.
- Synthetic-network examples: Examples cover each parameter combination of N and m at T = 0 and T = 0.9.
- Synthetic-network examples: At high temperature, the examples illustrate increased randomness and decreased clustering.
Real network datasets
The study evaluates methods on seven real social interaction networks, using undirected, unweighted graphs ordered primarily by node count and then by edge count.
- Dataset overview: Table 1 reports results for different methods on 7 real social interaction networks.
- Dataset organization: The networks are undirected and unweighted, and are ordered ascending by node count, with edge count breaking ties.
- Social and association networks: Zachary’s Karate Club contains 34 nodes and 78 edges, while the terrorist association network contains 62 nodes and 152 edges.
- Social interaction networks: The bottlenose-dolphin association network is described as a social network of frequent associations within a community in New Zealand.
- Collaboration and transportation networks: The jazz-musician collaboration network has 198 nodes and 2742 edges, and the USAir transportation network has 332 nodes and 2126 edges.
- Transportation networks: The American–Canadian city flight map contains 456 nodes and 37947 edges.