Technical Summary: Chordless Cycle Filtrations for Dimensionality Detection in Complex Networks via Topological Data Analysis

1. Problem Statement

Complex networks across diverse domains (biological, social, technological) often exhibit structural patterns consistent with an underlying latent hyperbolic geometry. Determining the effective dimensionality ($D$) of this latent space is crucial for understanding structural complexity, community organization, network navigation, and system dynamics. While various definitions of network dimensionality exist (e.g., fractal, spectral, metric), and model-driven approaches (such as the $S^D/H^{D+1}$ model) have successfully estimated dimensionality by projecting cycle frequencies onto configuration spaces, these methods often require generating large ensembles of synthetic surrogate networks for every new target network. This process is computationally intensive and lacks a unified, data-driven framework that integrates Topological Data Analysis (TDA) with machine learning to bypass surrogate generation.

Furthermore, standard TDA applications in network science have been limited. Ordinary persistent homology is ill-suited for graphs because cycles (1-dimensional features) have infinite persistence in the absence of higher-dimensional simplices to fill them. Additionally, existing filtration schemes (e.g., based on node degree or Ricci curvature) may not capture the specific geometric signatures required for dimensionality estimation.

2. Methodology

The authors propose a two-pronged approach combining algebraic topology and machine learning to estimate network dimensionality.

A. Chordless Cycle Filtrations and Extended Persistence

The core topological innovation is a weighting scheme based on chordless cycles (cycles with no internal chords).

1. Weighting: For a given network, three edge-weighted graphs are constructed. The weight of an edge is defined by the local density of chordless cycles of specific lengths: triangles ($C_t$), squares ($C_s$), and pentagons ($C_p$).
2. Extended Persistence: Since cycles in graphs do not die in standard filtrations, the authors compute extended persistence. This involves a technique to transform the edge-weighted graph into a topologically equivalent node-weighted graph via "degree-splitting subdivision." This allows the use of standard TDA software (Gudhi) to compute the extended persistence of cycles, defined as the difference between the birth value in the sublevel filtration and the birth value in the superlevel filtration.
3. Descriptors: The Total Extended Persistence (the sum of persistence values for all independent cycles) is calculated for each of the three filtrations, yielding a feature vector $(TP_t, TP_s, TP_p)$.

B. Dimensionality Estimation Approaches

The paper presents two methods for estimating $D$:

1. Surrogate-Based k-Nearest Neighbors (kNN):

   • For a target network, an ensemble of synthetic surrogates is generated using the $D$-GR (Geometric Randomization) procedure. This method rewires the network to maximize the likelihood of the $S^D/H^{D+1}$ model while preserving the exact degree sequence of the target.
   • The target network and its surrogates are mapped into a configuration space defined by $(TP_t, TP_s, TP_p)$.
   • A kNN classifier identifies the dimension $D$ of the surrogates closest to the target network.

2. Neural Network (DimNN):

   • To avoid generating surrogates for every new network, the authors train a Residual Multilayer Perceptron (DimNN).
   • Training Data: A database of 792,000 synthetic networks (SynNet) generated from the $S^D/H^{D+1}$ model with known dimensions ($D \in [1, 10]$) and varying parameters (degree heterogeneity $\gamma$, inverse temperature $\beta$).
   • Input Features: The model uses a 12-dimensional feature vector including:
     • Graph statistics: Number of nodes ($N$), average degree ($\langle k \rangle$), normalized second moment of degree distribution ($\langle k^2 \rangle / \langle k \rangle^2$), min/max degrees, and average neighbor degree ($\langle k_{nn} \rangle$).
     • Cycle densities: Mean chordless triangle, square, and pentagon densities ($C_t, C_s, C_p$).
     • Topological descriptors: Total extended persistences ($TP_t, TP_s, TP_p$).
   • Architecture: A deep MLP with 21 hidden layers, ReLU activations, dropout (50%), and residual connections, trained with AdamW.
   • Validation: A secondary regression model (using MSE loss) was trained to verify robustness, showing high agreement with the classification model.

3. Key Contributions

• Novel Filtration Scheme: Introduction of a chordless cycle density-based filtration scheme for graphs, specifically tailored to capture geometric properties relevant to dimensionality.
• Extended Persistence for Graphs: Adaptation of extended persistence to edge-weighted graphs via degree-splitting subdivision, enabling the computation of finite cycle lifetimes in network contexts where standard persistence fails.
• Data-Driven Dimensionality Estimation: Development of DimNN, a neural network trained on a massive synthetic database that can estimate network dimensionality directly from a single real-world network without generating surrogates.
• Integration of TDA and ML: Demonstration that TDA features (total persistence) significantly enhance the accuracy of machine learning models for dimensionality estimation, outperforming models using only cycle densities or degree statistics.

4. Results

• Correlation: A negative correlation was observed between network dimensionality and total extended persistence values, particularly for squares and pentagons (Pearson coefficients $\rho_s \approx -0.31$, $\rho_p \approx -0.24$).
• Synthetic Validation:
  • The kNN surrogate method achieved reasonable accuracy on synthetic targets, with confusion matrices showing high fidelity for most dimensions, though some confusion occurred between adjacent dimensions in highly heterogeneous networks.
  • DimNN achieved a classification accuracy of 83.00% on the validation set using the full feature vector.
  • Ablation studies confirmed that combining total persistence with mean cycle densities and degree-related features maximizes performance. Removing TDA features resulted in a significant drop in accuracy.
• Real-World Application:
  • The method was applied to 10 well-known real-world networks (e.g., Human Connectome, Jazz collaboration, Email networks). The inferred dimensions were consistent with previous literature (e.g., brain connectomes near $D=3$, social networks requiring slightly higher dimensions).
  • When applied to a larger dataset of 53 real networks, the model predicted dimensions ranging from 1 (Software, Web graphs) to 10 (some social networks).
  • Robustness: Two independently trained models (classification and regression) showed high agreement (up to 88.86% on synthetic data), suggesting the models capture underlying relationships rather than overfitting.
  • Validation: Surrogate networks generated using the predicted dimensions and D-Mercator embeddings successfully reproduced key topological properties of the original networks, including degree distribution, clustering spectrum, and percolation thresholds.

5. Significance and Claims

The paper claims that this work bridges the gap between complex network theory and Topological Data Analysis by providing a robust and effective method for uncovering the hidden geometry of complex networks.

• Efficiency: The neural network approach offers a significant computational advantage over previous surrogate-based methods, as it requires no retraining or surrogate generation for new networks.
• Expressiveness: The study demonstrates that cycle-aware filtrations and extended persistence descriptors are highly expressive features for dimensionality detection, complementing traditional geometric descriptors.
• Generalization: The model successfully transfers from synthetic training data to real-world networks, suggesting that the latent geometric structures of real networks are well-represented by the $S^D/H^{D+1}$ model within the tested parameter regimes.

The authors modestly note that the framework primarily targets geometric networks ($\beta > D$) and that extending the approach to weakly geometric regimes or optimizing the neural architecture for broader distribution shifts remains a direction for future work. The paper positions itself as a proof of concept for the utility of cycle-based filtrations in TDA and the feasibility of deep-learning-assisted dimensionality estimation.