Geometric Model Selection for Latent Space Network Models: Hypothesis Testing via Multidimensional Scaling and Resampling Techniques

Technical Summary: Geometric Model Selection for Latent Space Network Models

Problem Statement
Latent space models represent network ties as a function of the distance between nodes in an underlying low-dimensional geometric space. While Euclidean space has been the standard default, hyperbolic geometry is increasingly recognized for its ability to mimic realistic complex network patterns, such as tree-like structures, skewed degree distributions, and high clustering. A critical challenge in network analysis is determining which geometry (Euclidean vs. hyperbolic) underlies a specific observed network.

Previous approaches, such as those by Papamichalis et al. [2022], rely on comparing the "stress" (a goodness-of-fit metric) of Multidimensional Scaling (MDS) applied to observed geodesic distances (shortest path lengths) across different geometries. The method selects the geometry yielding lower stress. However, this paper identifies a significant limitation: comparing raw stress differences lacks statistical rigor and fails to account for uncertainty. Simulations demonstrate that this naive approach frequently misclassifies large, sparse Euclidean networks as hyperbolic, as the stress metric alone is insufficient to distinguish the underlying geometry reliably.

Methodology
To address the lack of statistical principledness in geometry selection, the authors propose two hypothesis testing frameworks that incorporate uncertainty, moving beyond simple stress comparison:

1. Permutation Tests (Nonparametric):
   Adapting standard MDS permutation tests to the network setting, the authors propose a density-preserving permutation scheme. Instead of permuting the geodesic distance matrix directly (which violates metric properties like the triangle inequality), the method permutes the adjacency matrix $Y$.

   • Procedure: The adjacency matrix is permuted to generate new networks $\tilde{Y}$ while preserving edge density. Only connected networks are retained. Classical and hyperbolic MDS are applied to the geodesic distances of these permuted networks to generate a null distribution of stress differences.
   • Hypothesis: The null hypothesis ($H_0$) posits that the observed difference in stress between geometries is indistinguishable from the difference obtained via random permutation.

2. Parametric Bootstrap via Conditional Latent Distance (J-Test Extension):
   The authors extend the Davidson-MacKinnon J-test to latent space network models. This method generates a parametric bootstrap distribution of networks conditioned on the observed geodesic distances and the Gaussian Latent Position Model (GLPM).

   • Theoretical Basis: Leveraging the GLPM, the authors derive the conditional distribution of latent distances $P(d_{ij} | \delta_{ij} = k)$, where $d_{ij}$ is the latent Euclidean distance and $\delta_{ij}$ is the observed geodesic distance. This allows for the generation of bootstrap networks that respect the observed network structure (specifically, the geodesic distances) rather than just edge density.
   • Procedure:
     1. Estimate parameters for the GLPM based on the observed network.
     2. Generate bootstrap networks by sampling latent distances from the conditional distribution $P(d_{ij} | \delta_{ij})$ and constructing new adjacency matrices.
     3. Compute the stress difference for each bootstrap sample.
     4. Calculate a p-value based on the proportion of bootstrap stress differences that are less than or equal to the observed stress difference.
   • Hypothesis: $H_0$ states that the hyperbolic model provides no additional explanatory power beyond the Euclidean model.

Key Results
The efficacy of these methods was evaluated through simulations on networks of varying sizes (15 to 200 nodes) and densities, as well as on real-world datasets.

• Simulation Findings:

  • Raw Stress Difference: Performs poorly on large and sparse networks, misclassifying almost all Euclidean networks as hyperbolic.
  • Permutation Test: Shows improved specificity (correctly identifying Euclidean networks) compared to raw stress differences but remains somewhat conservative, occasionally misclassifying hyperbolic networks. It demonstrates higher sensitivity for detecting hyperbolic structures in large networks.
  • Bootstrapped Networks: Offers a better balance between sensitivity and specificity. It significantly outperforms the raw stress difference method in distinguishing geometries for large, sparse networks, which are common in real-world data.
  • Limitations: The bootstrap method requires the generated networks to be connected. In cases with very low-degree nodes (e.g., the UKfaculty dataset), the resampling process frequently yields disconnected graphs, rendering the method inapplicable without modification.

• Real-World Applications:

  • Zachary's Karate Club: While raw stress favored a hyperbolic model, both the permutation test ($p=0.1053$) and bootstrap method ($p=0.1888$) failed to reject the null, suggesting Euclidean geometry is the better fit.
  • Other Datasets: Across four additional datasets (UKfaculty, adjnoun, dolphins, ffe friend), the uncertainty-aware methods provided more nuanced classifications than raw stress. For instance, while raw stress favored hyperbolic for the "ffe friend" network, the uncertainty methods suggested Euclidean was a better fit.

Significance and Claims
The paper claims that selecting a latent geometry based solely on MDS stress differences is statistically unsound and prone to error, particularly for large, sparse networks. The primary contribution is the adaptation of hypothesis testing frameworks (permutation and parametric bootstrap) to the latent space network setting to rigorously account for uncertainty.

The authors assert that:

1. Statistical Rigor: Incorporating uncertainty via permutation or bootstrapping prevents the systematic misclassification of Euclidean networks as hyperbolic.
2. Methodological Extension: The work successfully extends the Davidson-MacKinnon J-test to non-nested latent space models with differing geometries, utilizing the conditional distribution of latent distances given geodesic distances.
3. Practical Utility: The proposed methods are particularly effective for the "large and sparse" networks typical of real-world data, where simple stress comparison fails.

The authors remain modest regarding the limitations, noting that the bootstrap method is computationally expensive and currently dependent on the Gaussian LPM assumptions. They suggest future extensions could involve other latent space models (e.g., non-Gaussian links) or different baseline geometries (e.g., spherical), but do not propose specific new applications beyond the scope of the current simulation and real-data analysis.