Goodness-of-fit via count statistics in dense random simplicial complexes

Tadas Temčinas, Vidit Nanda, Gesine Reinert

Abstract

A key object of study in stochastic topology is a random simplicial complex. In this work we study a multi-parameter random simplicial complex model, where the probability of including a $k$-simplex, given the lower dimensional structure, is fixed. This leads to a conditionally independent probabilistic structure. This model includes the Erdős–Rényi random graph, the random clique complex as well as the Linial-Meshulam complex as special cases. The model is studied from both probabilistic and statistical points of view. We prove multivariate central limit theorems with bounds and known limiting covariance structure for the subcomplex counts and the number of critical simplices under a lexicographical acyclic partial matching. We use the CLTs to develop a goodness-of-fit test for this random model and evaluate its empirical performance. In order for the test to be applicable in practice, we also prove that the MLE estimators are asymptotically unbiased, consistent, uncorrelated and normally distributed.

Introduction

In modern network science, data is often represented as graphs consisting of nodes and edges. However, many real-world systems—ranging from chemical reactions to research collaborations—involve interactions between three or more entities simultaneously. Simplicial complexes are the primary mathematical tool in Topological Data Analysis (TDA) used to represent these higher-order relationships.

To perform rigorous statistical analysis on these structures, researchers require "null models": randomly generated complexes that serve as a baseline for comparison. While the $X(n, \mathbf{p})$ model is a powerful, multi-parameter random model, it has historically lacked the statistical machinery needed for practical application. This research fills that gap by deriving Maximum Likelihood Estimators (MLE) and developing a novel goodness-of-fit test to distinguish between purely combinatorial and geometric data structures.

The $X(n, \mathbf{p})$ Model and Parameter Estimation

The authors focus on the $X(n, \mathbf{p})$ model, where the probability of a group of vertices forming a high-dimensional "face" (simplex) depends on whether they already form the necessary lower-dimensional structure. For instance, a triangle (2-simplex) can only exist if its three constituent edges (1-simplices) are already present.

Key methodological contributions include:

  • MLE Derivation: The Maximum Likelihood Estimator for the probability vector $\mathbf{p}$ is shown to be the ratio of observed $i$-simplices to the number of "hollow" $i$-simplices (potential locations where they could have formed). The authors prove these estimators are asymptotically unbiased and consistent.
  • Stein’s Method: Because the presence of different simplices is not independent, the authors employ Stein’s method to prove Multivariate Central Limit Theorems (CLTs). This provides explicit bounds on how quickly the distribution of simplex counts approaches a normal distribution as the number of nodes ($n$) grows.

Overcoming the "Rank One" Trap

A significant discovery in this work is that in the "dense regime" (where probabilities do not vanish as the network grows), standard subcomplex counts—such as the number of triangles—become perfectly correlated in the limit. If one knows the number of edges, they asymptotically know the number of triangles and tetrahedra. This perfect correlation makes standard counts poor candidates for multivariate goodness-of-fit testing because the covariance matrix becomes singular.

To solve this, the authors turn to Discrete Morse Theory. By using critical simplex counts derived from a lexicographical acyclic partial matching, they identify statistics that maintain a "full rank" covariance matrix. These counts provide a much richer signal for statistical testing.

An illustration of an acyclic matching on a simplicial complex, used to identify critical simplices for statistical testing.

Goodness-of-Fit and Empirical Performance

The paper evaluates the proposed test using synthetic simulations to distinguish the $X(n, \mathbf{p})$ model from three geometric alternatives:

  1. Tetrahedron Model: A soft geometric model where 3D volumes are more likely to form if they are physically small.
  2. Triangle Model: A 2D version focusing on the area of triangles.
  3. Edge Model: A classical geometric random graph where edges form based on physical distance.

Using an interpolation process, the authors demonstrated that the goodness-of-fit test based on critical simplices is highly effective. It can distinguish the combinatorial $X(n, \mathbf{p})$ model from geometric models even when the geometric influence is subtle. Furthermore, the authors showed that while "centered triangle counts" are common in graph theory, they are less stable and more prone to parameter estimation errors than the proposed critical simplex counts.

Conclusion and Future Directions

This work provides the first rigorous statistical framework for a general class of random simplicial complexes. By providing explicit error bounds for their CLTs, the authors ensure these tests are theoretically sound for finite datasets.

Future research may explore the "sparse regime," where probabilities $p_k$ decrease as $n$ increases, potentially requiring Poisson approximations rather than normal ones. Additionally, incorporating the variance of the MLE itself into the test statistic could further enhance robustness in practical applications.

Summary updated

Abstract

A key object of study in stochastic topology is a random simplicial complex. In this work we study a multi-parameter random simplicial complex model, where the probability of including a $ k $-simplex, given the lower dimensional structure, is fixed. This leads to a conditionally independent probabilistic structure. This model includes the Erdős–Rényi random graph, the random clique complex as well as the Linial-Meshulam complex as special cases. The model is studied from both probabilistic and statistical points of view. We prove multivariate central limit theorems with bounds and known limiting covariance structure for the subcomplex counts and the number of critical simplices under a lexicographical acyclic partial matching. We use the CLTs to develop a goodness-of-fit test for this random model and evaluate its empirical performance. In order for the test to be applicable in practice, we also prove that the MLE estimators are asymptotically unbiased, consistent, uncorrelated and normally distributed.
BibTeX
@inproceedings{temcinas2025goodness,
  author = {Tadas Temčinas and Vidit Nanda and Gesine Reinert},
  title = {{Goodness-of-fit via count statistics in dense random simplicial complexes}},
  booktitle = {Foundations},
  year = {2025},
  doi = {10.3934/fods.2025013},
}
Figure