# Random Abstract Cell Complexes

Josef Hoppe
Department of Computer Science
RWTH Aachen University
Aachen, Germany
<EMAIL_ADDRESS>
&Michael T. Schaub
Department of Computer Science
RWTH Aachen University
Aachen, Germany
<EMAIL_ADDRESS>
https://hoppe.io

###### Abstract

We define a model for random (abstract) cell complexes (CCs), similiar to the
well-known Erdős–Rényi model for graphs and its extensions for simplicial
complexes. To build a random cell complex, we first draw from an Erdős–Rényi
graph, and consecutively augment the graph with cells for each dimension with
a specified probability. As the number of possible cells increases
combinatorially — e.g., 2-cells can be represented as cycles, or permutations
— we derive an approximate sampling algorithm for this model limited to two-
dimensional abstract cell complexes. Since there is a large variance in the
number of simple cycles on graphs drawn from the same configuration of ER, we
also provide an efficient method to approximate that number, which is of
independent interest. Moreover, it enables us to specify the expected number
of 2-cells of each boundary length we want to sample. We provide some initial
analysis into the properties of random CCs drawn from this model. We further
showcase practical applications for our random CCs as null models, and in the
context of (random) liftings of graphs to cell complexes. Both the sampling
and cycle count estimation algorithms are available in the package py-raccoon
on the Python Packaging Index.

_Keywords_ Random Models $\cdot$ Null Models $\cdot$ Random Abstract Cell
Complexes $\cdot$ Simple Cycles $\cdot$ Higher-Order Networks

††footnotetext: Evaluation Code and PyPI Package available at
github.com/josefhoppe/random-abstract-cell-complexes.

##  1 Introduction

Since the seminal work of Erdős–Rényi [1], random models of relational data
described by graphs have been a mainstay topic of interest within probability
theory, statistics, data science and machine learning. The interest in such
random graphs can be motivated from at least three perspectives. First, they
are vital as generative models for complex networks in various disciplines,
including social sciences, physics, and biology [2, 3], as they enable the
theoretical and empirical study of how certain (random) connection mechanisms
can influence the make-up of a network. Second, random models can serve as
null models to evaluate whether some observed network statistics may be deemed
significant. Third, random models can generate synthetic input data for
training machine learning models, or for controlled experiments and
benchmarking of network analysis algorithms.

Starting from the Erdős–Rényi (ER) model [1] and its variation by Gilbert [4]
a vast array of models for random graphs has been developed, such as the
Stochastic Block Model [5], the Configuration Model [6], etc. (see Appendix
for more related literature). Many of these models allow for the direct or
indirect specification of certain network statistics — e.g., density, triangle
counts, degree distribution — to be preserved (either exactly or in
expectation) in samples drawn from the model.

Recently, there has been a trend in studying higher-order network models such
as hypergraphs and simplicial and cellular complexes [7, 8, 9]. These richer
models for relational data have gained interest as they enable the study of
complex network structures with interactions beyond pairwise relationships,
which have been deemed to be essential to model certain systems. In contrast
to random graph models, the landscape of models for these higher-order
networks is however far less developed (see appendix for related work). In
particular, even though (abstract) cell complexes feature prominently in
topological data analysis [10], and in the emerging area of topological signal
processing [11, 12] and topological deep learning [13], there are hardly any
models for random abstract cell complexes. Appendix A provides a more in-depth
overview of related work.

Contributions. We define a model for random abstract cell complexes that
generalizes the Linial-Meshulam model [14, 15] for SCs. Our model may also be
used for random liftings of a given graph to a cell complex. We show that
sampling from this model is non-trivial due to the combinatorial increase in
the number of possible cells. Hence, we propose a novel algorithm to
approximately sample from the model, focussing on two-dimensional abstract
cell complexes. We provide an open source implementation of this algorithm in
python. As a secondary result, our work results in an approximation algorithm
to estimate the number of simple cycles in a graph, which may be of
independent interest. Finally, we demonstrate the utility of our random cell
complex model: we briefly analyze the orientability and homologies of sampled
complexes; use it as a null model to create an evaluation baseline; and
demonstrate the use of random liftings to gain insight to neural networks
defined on cell complexes [16].

Outline. In the remainder of this paper, we first introduces relevant concepts
and notation in Section 2 We then present our random cell complex model in
Section 3 and introduce an efficient approximate sampling algorithm for two-
dimensional abstract cell complexes in Section 4 . We analyze our algorithm
both theoretically in Section 5 and empirically in Section 7. Finally, we
provide some case studies on application of random CCs in Section 8.

Figure 1: Overview of the random abstract cell complex model. The model is
defined through iterative liftings from $d$ to $d+1$-dimensional cell
complexes. This makes it possible to fix a skeleton of the complex and only
apply the random lifting for subsequent dimensions. In this paper, we focus on
the lifting from one- to two-dimensional abstract cell complexes. For this, we
present a novel, efficient approximate sampling algorithm (see Figure 2).

##  2 Background and Notation

Graphs and simple cycles. We consider undirected graphs $G=(V,E)$ with
$n:=|V|$ nodes and $m:=|E|$ edges. An Erdős–Rényi random graph $G(n,p)$ has
$n$ nodes and for any node pair $u,v\in V$, the edge $(u,v)$ exists
independently with probability $p$. A cycle $c$ is a closed simple path on
$G$; its length $|c|$ equals the number of nodes (or edges) in $c$. We denote
the set of all cycles in $G$ by $C$. We use $C_{l}$ to denote the set of all
cycles $c\in C$ with length $|c|=l$ and $N_{l}=|C_{l}|$ to denote the number
of cycles on a graph. If node $u$ or edge $(u,v)$ is part of the cycle $c$, we
write $u\in c$ or $(u,v)\in c$, respectively.

Cycle bases and spanning trees. The cycle space of a graph is the set of its
subgraphs in which every node has even degree. With addition defined as the
symmetic difference and scalar multiplication with $\mathbb{F}_{2}$, the cycle
space is a vector space. A cycle basis is a set of _simple_ cycles that is a
basis of the cycle space. Any spanning tree $T$ on a graph $G$ induces a cycle
basis [17]: Each edge $(u,v)$ that is not in $T$ closes the path from $u$ to
$v$ on $T$, creating a simple cycle; the set of all induced cycles $C_{T}$ is
a cycle basis on $G$.

Uniform spanning trees and the Laplacian Random Walk. A uniform spanning tree
is a spanning tree picked uniformly at random from all spanning trees on a
given graph. Uniform spanning trees can be efficiently obtained by Wilson’s
algorithm [18]. The probability of a certain path being included in a uniform
spanning tree can be calculated via a particular absorbing random walk termed
the Laplacian random walk [19].

##  3 A model for random abstract cell complexes

Random abstract cell complexes can be sampled through a series of iterative
liftings, beginning with a set of $n$ nodes and iteratively adding higher-
dimensional cells. For two- and higher-dimensional cells, the number of
possible cells depends on the size of the boundary (e.g. edges for 2-cells).
Thus, for every dimension $d$ and possible boundary size $l$, we define the
inclusion probability $P^{(d)}_{l}$. Using these inclusion probabilities, we
can now define our random cell complex model
RCC$(n,P^{(1)},...,P^{(d_{\max})})$, where the vector $P^{(i)}=(P^{(i}_{l})$
collect the inclusion probabilities of $i$-cells with boundary size $l$. Each
possible cell is added independently according to the inclusion probability
(i.e., depending on the boundary size). For dimension $d=2$ and above, the
cells that can be added depend on the sampled cells from dimension $d-1$. This
iterative lifting-based model also allows us to augment any given CC with
random higher-dimensional cells of specified dimensions.

Relationship to the Erdős–Rényi model. For 1-cells (edges), the only possible
boundary size is $2$. Therefore, the model RCC$(n,P^{(1)})$ is equal to
ER$(n,P_{2}^{(1)})$.

Relationship to the Linial-Meshulam model. The RCC model can be seen as a
generalization of the LM model. Specifically, to recover the LM model, we set
$P^{(d)}_{d+1}=1$ for all dimensions $d$ except $d_{\max}$, resulting in a
full simplicial complex. Then, by setting $P^{(d_{\max})}_{d_{\max}+1}=p$ and
all other inclusion probabilities to $0$, we obtain the LM model.

Properties of Random Cell Complexes Before continuing, we provide some
empirical analysis on the properties of resulting cell complexes (obtained
using the sampling algorithm introduced below). To improve interpretability,
we discuss our results based on the number of sampled cells, rather than on
the probability $P^{(2)}$. First, in Figure 18(b), we can see that most
obtained CCs are not orientable, even with relatively few added cells. Second,
Figure 18(a) shows that in our experiments random CCs either have (almost) no
1-cohomology or (almost) no 2-cohomology. Qualitatively, these results also
hold for CCs randomly generated from point cloud triangulations. However,
these experiments are merely simple explorations performed with 1-skeletons
drawn from the ER model with the same parameters. More research is needed to
understand the behaviour of the RCC model in more detail, which is beyond the
scope of the current work.

##  4 Sampling Algorithms for Lifting to two-dimensional CCs

As a step towards a sampling algorithm for the full model described above, we
consider algorithms for the lifting from one-dimensional CCs (graphs) to two-
dimensional CCs. As there is no risk of confusion in this context, we simply
use $P_{l}$ toe refer to $P^{(2)}_{l}$ in the following.

###  4.1 Naïve sampling approaches

Rejection sampling for liftings of (nearly) complete graphs. A straightforward
and exact approach to selecting appropriate cells is rejection sampling using
random permutations of the nodes. More specifically, to sample a 2-cell with a
boundary of length $l$, we draw permutations of the nodes with length $l$
until we find a permutation that is a valid cycle on $G$. The rejection rate
depends on the underlying graph. If we ssume the graph to be sampled from ER,
then one of $p^{-l}$ permutations is a valid boundary of a 2-cell of length
$l$, in expectation. Therefore, rejection sampling is well-suited only for
sampling of short cells or on (almost) complete graphs, but too
computationally complex in other cases.

Markov Chain Monte Carlo. MCMC algorithms sample from a probability
distribution via random walks on all possible values, connected by a move set.
A simple move set on simple cycles would be the symmetric difference with any
set of simple cycles. However, this space may not be connected, e.g., on the
graph of two triangles connected by an edge (). Therefore, an MCMC algorithm
would require a more complex move set, i.e., there is no trivial Markov chain
Monte Carlo algorithm for sampling simple cycles.

###  4.2 An Approximate Algorithm for Lifting to two-dimensional abstract CCs

Start: 1-dim. CC
---
Sampling simple cycles (2-cells)
---
All cycles $C$
---
All cycles induced by ST
---
Cycle $c$ appears with prob. $\rho_{c}$
---
in set of induced cycles of a uniform ST
Select 2-cell enclosed by $l$ edges with prob. $P_{l}$
---
sampled cells
---
sampled cells
---
$s$ times
---
$s$ times
---
Pick $c$ with prob. $\rho^{\prime}_{c}\approx P_{l}/\rho_{c}s$
---
Output: 2-dim. CC
---
All Spanning Trees
---
pick uniformly
---
Figure 2: Random lifting from 1-dim. CC to 2-dim. CC and our sampling
algorithm. The model (strong background colors) is simulated by dividing it
into two steps (light background colors): First, $s$ uniform spanning trees
are sampled on the graph, each inducing a subset of all cycles. Depending on
the probability $\rho_{c}$ for any cycle to appear in such a subset, the
cycles are then sampled as cells. The algorithm (boxes) closely follows the
two-step sampling model, approximating $\rho_{c}$ for efficiency.

In this section, we introduce an efficient approximate sampling algorithm for
random 2-cells. On a high level, the sampling algorithm works as depicted in
Figure 2. It approximates sampling each cycle independently with a fixed
target probability $P_{l}$ from the (impractically large) set of all cycles in
$G$ with a two step sampling process. First, our algorithm samples $s$
spanning trees $T$. Each of these trees results in a subset of induced cycles
$C_{T}\subseteq C$. Note that every cycle $c$ has a certain occurence
probability $\rho_{c}$ to occur in such a set of cycles $C_{T}$. In the second
step, the algorithm selects cycles independently from these induced subsets,
each with a specific probability $\rho^{\prime}_{c}$ that is calculated to
obtain the desired target probability $P_{l}$.

Given the desired target sampling probability $P_{l}$, the occurence
probability $\rho_{c}$, and number of sampled trees $s$, we can calculate the
selection probability $\rho^{\prime}_{c}$ as follows. Note, that each cycle
$c$ has an independent probability of $\rho_{c}\rho^{\prime}_{c}$ to be
selected from each of the $s$ spanning trees. Hence we obtain the
relationship:

$\displaystyle
P_{l}=1-(1-\rho_{c}\rho^{\prime}_{c})^{s}\approx\rho_{c}\rho^{\prime}_{c}s\quad\Leftrightarrow\quad\rho^{\prime}_{c}=\frac{1-\sqrt[s]{1-P_{l}}}{\rho_{c}}\approx\frac{P_{l}}{\rho_{c}s}$
(1)

We remark that the above equation only has a valid solution for
$1-\sqrt[s]{1-P_{l}}<\rho_{c}$, i.e., only for sufficiently small target
probabilities $P_{l}$ or sufficiently large $s$. Otherwise,
$\rho^{\prime}_{c}$ could become greater than $1$. Since this occurs when the
number of sampled trees is too low, we call this behavior undersampling. Also
note that the sampled cells may be correlated, if we end up sampling multiple
cells from the same spanning tree.

As the occurcene probability is still expensive to compute, we introduce two
levels of approximations: a more accurate estimation denoted via tilde, and a
less accurate estimation with two tildes. For example, $\rho_{c}$ is
approximated by $\tilde{\rho}_{c}$ or
$\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}$, respectively. In line
with our original RCC model, the approximation assumes that the graph was
sampled from ER graph with (known) probability $p$. If the graph is given and
$p$ is not known, our approximation uses the maximum likelihood estimation
$p\approx{}m/\binom{n}{2}$.

Probability $\rho_{c}$ of cycles being induced by uniform spanning trees. To
determine the selection probability $\rho^{\prime}_{c}$ in accordance with the
target probability $P_{l}$, we have to estimate the occurence probability
$\rho_{c}$. Each cycle $c$ is induced by a spanning tree if and only if it
includes any path consisting of all but one edge of $c$. For each of these
paths, we can calculate the probability of it being included in a uniform
spanning tree via a so-called Laplacian Random Walk [19]. Since this walk is
computationally expensive to calculate, we approximate the probability through
multiple steps, most notably by approximating the 1-skeleton with the expected
graph where each edge has weight $p$, and by approximating some node degrees
with the expected degree. The full derivation of the formulae below can be
found in Appendix C. We denote the degree of $w$ by $d(w)$.

$\displaystyle\tilde{\tau}_{c}^{(l-1)}$
$\displaystyle=\frac{1}{1+\frac{(d(w)-2)}{n-3}\frac{n-l}{l}}$ (2)
$\displaystyle\tilde{\rho}_{c}$ $\displaystyle=\frac{\sum_{(u,v)\in
c}\tilde{\tau}_{c}^{(l-1)}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\left(\frac{n-2}{n}\right)^{l-3}\frac{n-1}{n}\frac{(n-1)q-1}{(n-1)q}$
(3) $\displaystyle\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}$
$\displaystyle=\frac{\sum_{(u,v)\in c}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\left(\frac{n-2}{n}\right)^{l-3}\frac{n-1}{n}\frac{(n-1)q-1}{(n-1)q}\frac{1}{1+\frac{(n-1)q-2}{n-3}\frac{n-l}{l}}$
(4)

##  5 Theoretical Considerations

In this section, we prove the algorithmic complexity of our sampling approach,
discuss theoretical limitations of spanning-tree-based sampling, and show that
a static configuration of our RCC model leads to heterogeneous two-dimensional
CCs.

###  5.1 Algorithmic Complexity

$=$
---
$+$
---
$+$
---
$-2$
---
$r$
---
$lca(u,v)$
---
$u$
---
$v$
---
$\pi$
---
$\sigma$
$d(u)-1...$
---
$d(u)-1...$
$\pi(r,u)$
---
$\sigma(r,u)$
$\pi(r,v)$
---
$\sigma(r,v)$
$\pi(r,lca)$
---
$\sigma(r,lca)$
Figure 3: Illustration of the efficient calculation based on the tree
structure.

######  Theorem 1.

On a connected 1-skeleton sampled from an ER model, our fast sampling
approximation can be calculated in
$\mathcal{O}(s\cdot{}m^{1+\varepsilon}+\ell)$, where $\ell$ is the sum of the
lengths of the boundaries of all resulting cells.

###### Proof.

We can use Wilson’s Algorithm [18] to efficiently sample spanning trees.
Wilson’s Algorithm is linear in the hitting time of the graph, i.e., the
expected time a random walk from any node to any other node takes. In the
worst case, the hitting time is $\mathcal{O}(n^{3})$ [20]. However, we are
assuming the graph to be sampled from an ER model with probability $p$ such
that the resulting graph is almost surely connected as the number of nodes
becomes large ($n\rightarrow\infty$). On these ER-Graphs, the hitting time is
in $\mathcal{O}(n)$ [21].

First, we decompose $\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}$
into three components: The sum component $\sigma=\sum_{(u,v)\in c}...$, the
product component $\pi=\prod_{w\in c}...$, and the remaining component
$\gamma(n,p,l)$, such that
$\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}=\sigma\cdot\gamma(n,p,l)/\pi$.
Instead of calculating the two components $\pi,\sigma$ over each cycle, we
utilize the spanning tree structure as illustrated in Figure 3: Given a
spanning tree, we choose an arbitrary root $r$. We define the components as
$\sigma(u,v)$ ($\pi(u,v)$) over the path from $u$ to $v$. For the empty path,
we define $\pi(r,r)=d(r)-1,\sigma(r,r)=0$. For a node $u$ with parent $v$, we
calculate $\pi(r,u)=\pi(r,v)\cdot(d(u)-1)$ and
$\sigma(r,u)=\sigma(r,v)+(d(v)-1)(d(u)-1)$. For any nodes $u,v$:

$\displaystyle\pi(u,v)$
$\displaystyle=\frac{\pi(r,u)\pi(r,v)(d(\text{lca}(u,v))-1)}{\pi(r,\text{lca}(u,v))^{2}}$
(5) $\displaystyle\sigma(u,v)$
$\displaystyle=\sigma(r,u)+\sigma(r,v)-2\sigma(r,\text{lca}(u,v))+(d(v)-1)(d(u)-1)$
(6)

This only covers the path, thus we close the cycle:
$\pi=(d(u)-1)(d(v)-1)\pi(u,v)$ and $\sigma=(d(u)-1)(d(v)-1)+\sigma(u,v)$,
respectively. Both components take $\mathcal{O}(n)\leq\mathcal{O}(m)$ to
calculate per tree. For a more detailed example on a toy graph, see Appendix
B.

To compute the lowest common ancestor (lca) of two nodes, we use Tarjan’s off-
line lca algorithm [22], which runs in $\mathcal{O}(n+m\alpha(n+m))$ (per
tree), where $\alpha$ is the inverse of the Ackermann function. On a connected
graph, the number of edges is, asymptotically, at least as large as the number
of nodes, i.e., we can simplify the complexity of lca to
$\mathcal{O}(m\alpha(m))\leq\mathcal{O}(m^{1+\varepsilon})$ for any
$\varepsilon>0$.

Note that we only need to completely enumerate the cells that are sampled.
When a cell is selected, we take the two nodes it is induced by and walk from
each to their lowest common ancestor, thus obtaining the boundary; and taking
$\Theta(\ell)$ steps over all spanning trees.

The theorem follows from the sum of these complexities. ∎

For the non-approximated estimation, it takes
$\mathcal{O}(s\cdot{}m\cdot{}l)\leq\mathcal{O}(s\cdot{}m\cdot{}n)$, where $l$
is the average length of occurring cycles, to calculate the probabilities
instead. In contrast, calculating $\rho_{c}$ exactly needs at least
$\Omega(smn^{2})$.

###  5.2 Theoretical Limitations

Before investigating the accuracy of our estimation approach in practice, we
consider some theoretical limitations of spanning-tree-based cycle sampling.

To this end, let us consider the complete graph $K_{n}$, on which the prior
estimation of the number of cycles $\mathcal{N}_{l}$ and our approximated
occurence probability $\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}$
are exact. Overall, longer cycles are less frequently induced by a spanning
tree (compare Figure 5(a)), since the probability of any cycle being induced
converges faster to zero than the number of possible cycles grows. As we will
see later, this also holds for smaller values of $p$.

Overcoming this would require an impractically large number of samples. In the
worst case, the expected number of sampled cells $c$ with length $l=n$ in one
spanning tree is:

$\displaystyle
N_{l}\rho_{c}=\frac{n!}{(n-n)!}\frac{1}{2l}\cdot\frac{l}{1+\frac{n-l}{n}}\frac{(n-2)^{2}}{n^{n-2}}=\frac{n!}{2}\frac{(n-2)^{2}}{n^{n-2}}$
(7)

In other words, we would need to sample $\frac{1}{N_{l}\rho_{c}}\approx
2.2\cdot 10^{34}$ spanning trees to get a single cycle for $n=l=100$ in
expectation.

###  5.3 Heterogeneity for static target probability $P_{l}$

With a fixed probability $P_{l}$ for each possible cell to be sampled, given
the same parameter configuration, some sampled CCs will have ten times the
expected 2-cells while others have none. We can estimate the number of cells
from the a priori estimation of the number of simple cycles $\mathcal{N}_{l}$
and the target probability $P_{l}$. However, as Figure 9 shows, there is a
large variance in the correct count $N_{l}$, which translates to a similar
variance in the number of cells. For practical applications, this behavior may
be important to consider. If required, this behavior can be changed by
adjusting $P^{(2)}$ based on the realization of the 1-skeleton. However, while
the total number of edges in a graph is easy to calculate, the total number of
simple cycles is not.

##  6 Obtaining more homogenous cell complex configurations based on cycle
count estimation

In practical applications, the large heterogeneity in the number of 2-cells
arising from a fixed $P_{l}$ can be a problem. For a graph with $N_{l}$ cycles
of length $l$, we expect a total of $P_{l}\cdot{}N_{l}$ 2-cells. Given the
number of cycles $N_{l}$, we could therefore adjust $P_{l}$ to result in a
desired number of 2-cells with boundary length $l$ (in expectation). However,
in contrast to the number of edges, the number of cycles $N_{l}$ is not
trivial to compute for an arbitrary length $l$ [23] and accurate methods are
computationally inefficient. Therefore, we introduce an approximation
algorithm that works similar to our sampling algorithm: We estimate the number
of cycles with length $l$ by simulating sampling from $s$ spanning trees with
$P_{l}=1$. In contrast to actual sampling, we do not explicitly identify all
induced cycles. Therefore, a cycle that occurs in multiple sampled spanning
trees will also be counted multiple times. Thus, to achieve a desired
probability $P_{l}$ to count cells, we introduce the counting coefficent
$\rho_{c}^{\prime\prime}$:

$P_{l}=\rho_{c}\rho^{\prime\prime}_{c}s\Rightarrow\rho^{\prime\prime}_{c}=\frac{P_{l}}{\rho_{c}s}=\frac{1}{\rho_{c}s}\quad\text{for
$P_{l}=1$}$ (8)

Below, we motivate that the sum counting coefficients
$\rho_{c}^{\prime\prime}$ of induced cycles approximates the count of all
cycles $N_{l}$: $N_{l}\approx\sum_{T}\sum_{c\in C_{l}\cap
C_{T}}\rho^{\prime\prime}_{c}$.

Given a graph $G$, let $\mathbb{T}$ be the set of all spanning trees of $G$
and $\mathbb{T}_{c}\coloneqq\\{T\in\mathbb{T}:c\in C_{T}\\}$ the set of all
spanning trees that induce a given cycle $c$. Note that the occurence
probability $\rho_{c}$ of a cycle $c$ can be expressed in terms of the
cardinalities of these sets of spanning trees, i.e.,
$\rho_{c}=\nicefrac{{|\mathbb{T}_{c}|}}{{|\mathbb{T}|}}$. In the ideal case,
where we iterate over all trees $\mathbb{T}$ and the number of samples
$s=|\mathbb{T}|$ is the number of all spanning trees, this accurately counts
all cycles:

$N_{l}=\sum_{c\in C_{l}}1=\sum_{c\in
C_{l}}\sum_{T\in\mathbb{T}_{c}}\frac{1}{|\mathbb{T}_{c}|}=\sum_{T\in\mathbb{T}}\sum_{c\in
C_{l}\cap C_{T}}\frac{1}{|\mathbb{T}_{c}|}=\sum_{T\in\mathbb{T}}\sum_{c\in
C_{l}\cap C_{T}}\frac{1}{\rho_{c}|\mathbb{T}|}=\sum_{T\in\mathbb{T}}\sum_{c\in
C_{l}\cap C_{T}}\rho_{c}^{\prime\prime}$ (9)

In practice, we effectively approximate $\mathbb{T}$ with uniformly sampled
spanning trees $T_{1},...,T_{s}$ for a relatively small number of samples
$s\ll|\mathbb{T}|$. Practical numbers of samples $s$ tend to result in
counting coefficients $\rho^{\prime\prime}_{c}$ that are greater than $1$.
Summing these counting coefficents $\rho^{\prime\prime}_{c}$ of all induced
cycles results in the desired approximation:

$\displaystyle N_{l}\stackrel{{\scriptstyle\mathclap{\mbox{(\ref{eq:counting-
ideal})}}}}{{=}}\sum_{T\in\mathbb{T}}\sum_{c\in C_{l}\cap
C_{T}}\frac{1}{\rho_{c}|\mathbb{T}|}\approx\frac{|\mathbb{T}|}{s}\sum_{i=1}^{s}\sum_{c\in
C_{l}\cap C_{T_{i}}}\frac{1}{\rho_{c}|\mathbb{T}|}=\sum_{i=1}^{s}\sum_{c\in
C_{l}\cap
C_{T_{i}}}\frac{|\mathbb{T}|}{s}\cdot{}\frac{1}{\rho_{c}|\mathbb{T}|}=\sum_{i=1}^{s}\sum_{c\in
C_{l}\cap C_{T_{i}}}\rho^{\prime\prime}_{c}$ (10)

Figure 4: The cycle count estimation uses the same basic structure as the
sampling algorithm. The occurring cycles and their occurence probabilities can
be used to estimate the total number of cycles: The expected number of induced
cycles with length $l$ is the sum of the occurence probabilities of all such
cycles. To estimate the total number, we can invert this idea: For every
occuring cycle $c$ there are (approximately speaking)
$\nicefrac{{1}}{{\rho_{c}}}$ cycles with the same occurence probability: This
results in sampling, in expectation,
$\rho_{c}\cdot{}\nicefrac{{1}}{{\rho_{c}}}=1$ occuring cycle. The approach,
again, samples $s$ spanning trees, taking the average cycle count estimation.

An alternative interpretation based on individual cycles is illustrated in
Figure 4: Given a spanning tree $T$, we can use the induced cycles $C_{T}$ and
their occurence probabilities to estimate the total number of cycles on the
graph: First, we assume that the occurence probabilities $\rho_{c}$ of the
induced cycles are representative of all occurence probabilities of cycles of
the same length. Second, on average, if a cycle $c$ of length $l$ occurs with
probability $\rho_{c}$, there are $\nicefrac{{1}}{{\rho_{c}}}$ cycles with
that length. Finally, to improve the accuracy of this estimate, we average the
result over $s$ spanning trees.

Note that the accuracy of the estimation depends on how accurately the
occuring cycles represent the distribution of cycles (with regard to both the
cycle lengths and occurence probabilities) induced by spanning trees. With
sufficiently many samples, the law of large numbers says that the cycles will
be representative, i.e., the estimate will be accurate. It is unclear how to
determine the number of samples required for the approximation to become
accurate. However, the number of induced cycles of each length can serve as an
indicator: If there are only few or even a single induced cycle for a certain
length $l$, we don’t have confidence in the estimated number $N_{l}$. Thus, we
also count the number of occurences $o_{l}=\sum_{T_{i}}|C_{l}\cap C_{T_{i}}|$.

Sampling with expected number of cells To ensure a sufficently accurate
estimation of $N_{l}$, we only sample cells with boundary lengths $L:=\\{3\leq
l\leq n:o_{l}>t\\}$ that occur more often than a user-specified threshold $t$.
Calculating $P_{l}$ to achieve any desired number in expectation is now
simple; if desired, one can also distribute an overall number evenly over all
occuring lengths. In this paper, we use $\nu$ to denote an expected number of
cells evenly distributed among occurring lengths.

##  7 Empirical Evaluation of the Sampling Algorithm

(a) Cycle count estimation on the complete graph $K_{100}$; 50 different runs
shown.

(b) Cycle count estimation on 50 graphs sampled from ER with $n=20,p=0.3$.

Figure 5: The cycle count estimation
$\smash{\raisebox{0.0pt}[8.0pt]{$\tilde{\raisebox{0.0pt}[7.2pt]{$\tilde{\raisebox{0.0pt}[6.2pt]{$N$}}$}}$}_{l}}$
and the actual number of cycles $N_{l}$ (red). With increasing $l$, cycles
become less likely to be induced by a spanning tree. This results in a lower
accuracy and estimates of
$\raisebox{0.0pt}[8.0pt]{$\tilde{\raisebox{0.0pt}[7.2pt]{$\tilde{\raisebox{0.0pt}[6.2pt]{$N$}}$}}$}_{l}=0$
for larger $l$.

The evaluation code is available under github.com/josefhoppe/random-abstract-
cell-complexes.

###  7.1 Sampling Accuracy

(a) Estimated Occurence Probability $\tilde{\rho}_{c}$

(b) Approximated Occurence Probability
$\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}$

Figure 6: The estimated (a) and approximated (b) occurence probability of
simple cycles on one graph sampled from ER with $n=30,p=0.5$; cycles for
evaluation obtained from $10$ uniform STs. Both methods are very close to the
correct probabilities. Especially for shorter cycles, the estimated
probability is more accurate. This is to be expected, as for longer cells, the
relative variance is naturally smaller and the likelihood of the last step is
less dependent on the degree.

First, we compare our approximations to estimate the occurence probability
$\tilde{\rho}_{c}$. We evaluate this by first sampling a single graph from an
ER model, then sampling multiple spanning trees, and calculating the $\rho$s
for all cycles induced by the spanning trees.

Figure 6 shows that, given a sufficiently large number of nodes $n$ and
connection probability $p$, both approximations of $\rho$ are very accurate.
However, as Figure 10 shows, that for graphs that are relatively sparse the
accuracy drops. This is likely a result of graphs with smaller edge
probabilities behaving more differently from the expected graph: Our
approximation assumes a relatively densely and evenly connected graph. Sparse
configurations of ER are more likely to deviate from this expectation than
dense configurations: The degree distribution is less uniform and a path is
more likely to ‘cut off’ parts of the graph due to the lower connectivity.

On graphs that are not densely and evenly connected, our approximation still
utilizes the degree of nodes on the induced cycles, providing some accuracy. A
comparison with Figure 11 shows that, on both sparse and dense graphs, our
approximation is much more accurate than assigning each cycle the average
probability of all cycles with the same length.

We evaluate the accuracy of the cycle count estimation by also calculating the
correct number of cycles. For ER-Graphs, this means we have to choose small
instances to sample from, making it possible to enumerate all cycles.
Additionally, on the full graph, we can easily calculate the number of simple
cycles, making it suitable for a comparison of the performance on larger
graphs.

Given the good accuracy of the occurrence probability approximation, we expect
the cycle count estimation to be similarly accurate, with the added condition
that sufficiently many cells of the given length were induced by the sampled
spanning trees. Figure 5(b) confirms this expectation, showing a slight
overestimation for smaller lengths and a large increase in the error for
longer cells. Furthermore, our experiments on the full graph (Figure 5(a))
show that the increase in error for longer cells is a result of the small
number of sampled cycles since, on the full graph, all cells are the same and
the estimated probability is always correct. This is exactly in line with our
theoretical considerations.

Overall, the sampled number of cells that is very close to the desired number,
as shown in Figure 17. Note that any skew of the occurrence probability
results in an equal but opposite skew in the estimated number of cycles,
leading in total to an accurate number of cells sampled.

###  7.2 Accuracy of random liftings on non-ER graphs

Our general random cell complex model can also be used to describe random cell
complexes with a fixed $d$-skeleton. Our sampling algorithm can therefore be
leveraged to provide a random lifting of any graph to a two-dimensional cell
complex. However, given that our approximations used in the sampling procedure
are based on the assumption that the graph was sampled from ER, we expect a
lower accuracy.

Figure 12(a) shows the estimation accuracy on a graph sampled from a
homophilic configuration of the SBM. Interestingly, the overall accuracy is
still quite close to the accuracy on ER graphs. In fact, this pattern also
holds for heterophilic graphs, shown in Figure 12(b). Our findings extend even
to the case of a complete bipartite graph, although, as Figure 14 shows, we do
see a small but consistent overestimation of the number of cycles.
Furthermore, the approximated occurrence probability $\rho_{c}$ is
surprisingly good in both cases (cf Figure 13).

So far, we have only evaluated our algorithm on graph models that have regular
shapes, with all nodes symmetric in expectation. Figure 15 shows the result on
graphs sampled from the Barabasi-Albert model and a Configuration model with
an uneven degree distribution. The accuracy is comparable to the accuracy on
graphs sampled from the SBM, i.e., still higher than expected.

Overall, in our experiments, any deviation from an evenly and densely
connected graph reduces the accuracy of our estimation: Communities, overall
low connectivity, or uneven degree sequences make the estimation less
accurate. Therefore, we expect a similar behavior on real-world graphs: It
should work well on graphs with relatively evenly distributed degrees that are
evenly and densely connected. Figure 16 shows that our experiments are in line
with this expectation: Zachary’s Karate Club, which famously consists of two
communities, is estimated less accurately than the November 17 network, which
also has a higher average node degree.

###  7.3 Time complexity

Figure 7: Runtime for $\nu=10n,s=1000$.

Figure 7 shows that our approach is highly scalable. In configurations where
the approximated occurrence probability is worse, the estimated is also
relatively efficient. Empirically, the runtimes for both approaches are in
line with our analysis: The slower estimation takes approximately
$\mathcal{O}(n^{2.6})$; the faster approximation takes approximately
$\mathcal{O}(n^{2})$, which is consistent with
$\mathcal{O}(s\cdot{}m^{1+\varepsilon})$ since $m\in\Theta(n^{2})$ for a fixed
$p$.

##  8 Applications

In this section, we explore the use cases for random cell complexes we
identified earlier. We focus on minimal examples showcasing the usage rather
than a comprehensive analysis.

Figure 8: Comparison of the approaches to the flow representation learning
problem from [24] and using random CCs (Anaheim dataset [25])111Code available
at github.com/josefhoppe/random-abstract-cell-complexes..

###  8.1 Null Model as Experiment Baseline

When evaluating novel methods that infer cells, it is useful to have a
baseline that marks randomness. In the case of the flow representation
learning problem [24], we see that random 2-cells are very inefficient in
Footnote 1. However, this also gives us a way to classify the performance of
the approaches we want to evaluate. In this case, we see that the newly
proposed methods give a representation that provides a significant improvement
over triangles, but triangles is already a method that explains a lot of
structure.

###  8.2 Sensitivity analysis: how important are higher-order interactions?

In this section, we demonstrate the use of random CCs for the sensitivity (or
ablation analysis [26]) of neural networks defined on higher-order networks.

In [16], Bodnar et al. propose a novel architecture for cell complex neural
networks (CWNs). To obtain a cell complex and capture structural information
on a graph, they add chordless cycles as 2-cells. On the synthetic
RingTransfer benchmark, the authors demonstrate that 2-cells also improve the
propagation of node features. Here we use our random cell complex model to
investigate in how far this specific choice of 2-cells is relevant or if
adding random cells would have yielded similar results. This provides insights
into whether it is the _specific_ cell structure (adding chordless cycles)
that conveys an advantage, or whether it is merely the increase in expressive
power of the neural networks (resulting from adding higher-order cells) that
is of importance.

Table 1: Comparison of CWN [16] with the original 2-cells (’Rings’), random 2-cells (’RND’), and no 2-cells (’None’). Code available at github.com/josefhoppe/cwn-random-ccs. Results deviate slightly from [16] despite using the original code. Accuracy of PPGNs from [16]. Dataset [27] | PROTEINS | NCI109
---|---|---
CWN (Rings) | $73.8\pm 4.3$ | $\mathbf{84.5\pm 1.6}$
CWN (RND) | $74.2\pm 5.0$ | $82.2\pm 1.3$
CWN (None) | $73.0\pm 5.5$ | $82.9\pm 1.2$
PPGNs [28] | $\mathbf{77.2\pm 4.7}$ | $82.2\pm 1.4$

Interestingly, for the PROTEINS dataset (see Table 1) there is no significant
performance difference if we simply add random 2-cells instead of following
the procedure outlined in [16]. Indeed, a similar performance can even be
gained by not adding any 2-cells at all. In contrast, on the NCI109 dataset
[27], adding random 2-cells significantly decrease the accuracy. This
observation indicates that the 2-cell lifting procedure proposed in [16] works
as intended on NCI109, but fails to capture relevant topological information
on PROTEINS beyond what we could expect by simply increasing the expressivity
of the network. To corroborate our findings, we have added a further
comparison to the PPGN architecture [28]. PPGN also features an increased
expressivity compared to standard GNNs, but is not based on any topological
considerations. As Table 1 shows PPGN works well in the PROTEIN dataset, yet
only performs as good as adding random cells in CWN. In conclusion, this
example hints at how random cell complexes can lead to further insights into
what features drive the performance of higher-order GNNs.

##  9 Conclusion

The main contributions of this paper are (i) the introduction of a simple
model for random abstract cell complexes, (ii) an efficient approximate
sampling algorithm for this model, and (ii) a cycle count estimation algorithm
required to make the model more amenable to application scenarios, in which we
want to fix the number of certain cells in expectation. We explored some
properties of this model and showcased how it enables a number of
investigations concerning higher-order network data and learning methods
operating with such data: Specifically, random CCs can be used as synthetic
input data and as null models for multiple purposes.

This groundwork opens up multiple avenues for future research on abstract cell
complexes: First, a more theoretical analysis of the number of simple cycles
and the behavior of RCCs. Second, while we defined our model for arbitrary
dimensions, higher-dimensional cells add considerable combinatorial
complexity, which is why we limited our sampling algorithm to 2-cells. Indeed,
adapting our sampling algorithm to higher-order cells is not trivial as the
higher-dimensional analogues of spanning trees do not share many of their
desirable properties.

When employing random cell complexes as synthetic data, it may also be
desirable to include more structure in the cell complexes, both on the edge
and cell levels. On the level of 2-cells, a simple extension could introduce a
block structure and modify the sampling probabilities based on block
membership.

Finally, the cycle count estimation is useful in its own right. To ensure it
is suitable for the task, future work should evaluate its accuracy and compare
it further to previous approaches, which is out of scope for this paper.

## Acknowledgements

Funded by the European Union (ERC, HIGH-HOPeS, 101039827). Views and opinions
expressed are however those of the author(s) only and do not necessarily
reflect those of the European Union or the European Research Council Executive
Agency. Neither the European Union nor the granting authority can be held
responsible for them.

## References

  * [1] Paul Erdős and Alfréd Rényi,  “On random graphs I,”  Publ. math. debrecen, vol. 6, no. 290-297, pp. 18, 1959.
  * [2] Réka Albert and Albert-László Barabási,  “Statistical mechanics of complex networks,”  Reviews of modern physics, vol. 74, no. 1, pp. 47, 2002.
  * [3] Mikhail Drobyshevskiy and Denis Turdakov,  “Random graph modeling: A survey of the concepts,”  ACM computing surveys (CSUR), vol. 52, no. 6, pp. 1–36, 2019.
  * [4] Edgar N Gilbert,  “Random graphs,”  The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959.
  * [5] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt,  “Stochastic blockmodels: First steps,”  Social networks, vol. 5, no. 2, pp. 109–137, 1983.
  * [6] Bailey K Fosdick, Daniel B Larremore, Joel Nishimura, and Johan Ugander,  “Configuring random graph models with fixed degree sequences,”  Siam Review, vol. 60, no. 2, pp. 315–355, 2018.
  * [7] Christian Bick, Elizabeth Gross, Heather A Harrington, and Michael T Schaub,  “What are higher-order networks?,”  SIAM Review, vol. 65, no. 3, pp. 686–731, 2023.
  * [8] Leo Torres, Ann S Blevins, Danielle Bassett, and Tina Eliassi-Rad,  “The why, how, and when of representations for complex systems,”  SIAM Review, vol. 63, no. 3, pp. 435–485, 2021.
  * [9] Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri,  “Networks beyond pairwise interactions: Structure and dynamics,”  Physics Reports, vol. 874, pp. 1–92, 2020.
  * [10] Larry Wasserman,  “Topological data analysis,”  Annual Review of Statistics and Its Application, vol. 5, pp. 501–532, 2018.
  * [11] Sergio Barbarossa and Stefania Sardellitti,  “Topological signal processing over simplicial complexes,”  IEEE Transactions on Signal Processing, vol. 68, pp. 2992–3007, 2020.
  * [12] Michael T Schaub, Yu Zhu, Jean-Baptiste Seby, T Mitchell Roddenberry, and Santiago Segarra,  “Signal processing on higher-order networks: Livin’on the edge… and beyond,”  Signal Processing, vol. 187, pp. 108149, 2021.
  * [13] Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenz, Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K Dey, Soham Mukherjee, Shreyas N Samaga, et al.,  “Topological deep learning: Going beyond graph data,”  arXiv preprint arXiv:2206.00606, 2022.
  * [14] Nathan Linial* and Roy Meshulam*,  “Homological connectivity of random 2-complexes,”  Combinatorica, vol. 26, no. 4, pp. 475–487, 2006.
  * [15] Armindo Costa and Michael Farber,  “Random simplicial complexes,”  in Configuration Spaces: Geometry, Topology and Representation Theory, pp. 129–153. Springer, 2016.
  * [16] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein,  “Weisfeiler and lehman go cellular: Cw networks,”  Advances in Neural Information Processing Systems, vol. 34, pp. 2625–2640, 2021.
  * [17] Maciej Marek Sysło,  “On cycle bases of a graph,”  Networks, vol. 9, no. 2, pp. 123–132, 1979.
  * [18] David Bruce Wilson,  “Generating random spanning trees more quickly than the cover time,”  in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 296–303.
  * [19] JW Lyklema, Carl Evertsz, and L Pietronero,  “The laplacian random walk,”  Europhysics Letters, vol. 2, no. 2, pp. 77, 1986.
  * [20] Graham Brightwell and Peter Winkler,  “Maximum hitting time for random walks on graphs,”  Random Structures & Algorithms, vol. 1, no. 3, pp. 263–276, 1990\.
  * [21] Matthias Löwe and Felipe Torres,  “On hitting times for a simple random walk on dense erdös–rényi random graphs,”  Statistics & Probability Letters, vol. 89, pp. 81–88, 2014.
  * [22] Robert Endre Tarjan,  “Applications of path compression on balanced trees,”  Journal of the ACM (JACM), vol. 26, no. 4, pp. 690–715, 1979.
  * [23] Pierre-Louis Giscard, Nils Kriege, and Richard C Wilson,  “A general purpose algorithm for counting simple cycles and simple paths of any length,”  Algorithmica, vol. 81, pp. 2716–2737, 2019.
  * [24] Josef Hoppe and Michael T Schaub,  “Representing edge flows on graphs via sparse cell complexes,”  in The Second Learning on Graphs Conference, 2023.
  * [25] Transportation Networks for Research Core Team,  “Transportation networks for research,” 2020,  Accessed: 2024-01-29.
  * [26] Chris Fawcett and Holger H Hoos,  “Analysing differences between algorithm configurations through ablation,”  Journal of Heuristics, vol. 22, pp. 431–458, 2016.
  * [27] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann,  “TUDataset: A collection of benchmark datasets for learning with graphs,”  arXiv preprint arXiv:2007.08663, 2020.
  * [28] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman,  “Provably powerful graph networks,”  Advances in neural information processing systems, vol. 32, 2019\.
  * [29] Pim van der Hoorn, Gabor Lippner, and Dmitri Krioukov,  “Sparse maximum-entropy random graphs with a given power-law degree distribution,”  Journal of Statistical Physics, vol. 173, pp. 806–844, 2018.
  * [30] Duncan J Watts and Steven H Strogatz,  “Collective dynamics of ‘small-world’networks,”  nature, vol. 393, no. 6684, pp. 440–442, 1998.
  * [31] Jesper Dall and Michael Christensen,  “Random geometric graphs,”  Physical review E, vol. 66, no. 1, pp. 016121, 2002.
  * [32] Matthew Kahle,  “Topology of random clique complexes,”  Discrete mathematics, vol. 309, no. 6, pp. 1658–1671, 2009.
  * [33] Matthew Kahle et al.,  “Topology of random simplicial complexes: a survey,”  AMS Contemp. Math, vol. 620, pp. 201–222, 2014.
  * [34] Martina Zähle,  “Random cell complexes and generalised sets,”  The Annals of Probability, pp. 1742–1766, 1988.
  * [35] Benjamin Schweinhart, Jeremy K Mason, and Robert D MacPherson,  “Topological similarity of random cell complexes and applications,”  Physical Review E, vol. 93, no. 6, pp. 062111, 2016.
  * [36] Lutz Leistritz and Martina Zähle,  “Topological mean value relations for random cell complexes,”  Mathematische Nachrichten, vol. 155, no. 1, pp. 57–72, 1992.
  * [37] Chris Whong,  “FOILing nyc’s taxi trip data,” 2014,  https://chriswhong.com/open-data/foil_nyc_taxi/. Last Accessed 2024-03-28.
  * [38] Stefania Sardellitti, Sergio Barbarossa, and Lucia Testa,  “Topological signal processing over cell complexes,”  in 2021 55th Asilomar Conference on Signals, Systems, and Computers. IEEE, 2021, pp. 1558–1562.
  * [39] Oded Schramm,  “Scaling limits of loop-erased random walks and uniform spanning trees,”  Israel Journal of Mathematics, vol. 118, no. 1, pp. 221–288, 2000\.
  * [40] Wayne W Zachary,  “An information flow model for conflict and fission in small groups,”  Journal of anthropological research, vol. 33, no. 4, pp. 452–473, 1977.
  * [41] CJ Rhodes and P Jones,  “Inferring missing links in partially observed social networks,”  Journal of the operational research society, vol. 60, no. 10, pp. 1373–1383, 2009.

##  Appendix A Related Work

Random graph models. Random graph models started with the Erdős–Rényi random
graph model [1], which originally proposed to draw a graph uniformly at random
from the set of all graphs with a fixed number of nodes and edges. In this
paper, we refer to a variant introduced by Gilbert [4] but commonly also
referred to as Erdős–Rényi model, that draws each edge independently with
probability $p$. More complex graph models generally focus on modeling
community structure (most notably the Stochastic Block Model [5]) or the
distribution of node degrees [2, 29]. Furthermore, there are models aimed to
more closely approximate real-world networks, such as the Watts-Strogatz
small-world graph [30], modeling the small diameter of real-world networks.
Finally, graphs may be generated from random point clouds by connecting nodes
that are close to each other in metric space [31]; resulting in the formation
of clusters similar to real-world networks. There are many more models and
ways to configure models that would exceed the scope of this literature
review, but it should be noted that many use cases for these models exist,
requiring different graph models.

Random simplicial complex models. The Linial-Meshulam model for random SCs
[14] is an extension of Erdős–Rényi to higher dimensions. LM takes a complete
$(d-1)$-dimensional complex and samples i.i.d. from all possible
$d$-simplices. The Linial-Meshulam model was generalized in multiple ways,
e.g. a different static probability $P_{d}$ to sample $d$-simplices
(separately) for each dimension (i.e., cardinality) $d$ [15]. In a similar
vein to our model, random clique complexes [32], i.e., SCs obtained by adding
all cliques of a random graph as simplices, build on a graph as a 1-skeleton.
We refer to [33, 15] for a more detailed overview of existing models. To date,
no SC model analogues to many of the well-known random graph models (e.g.
modeling community structure, degree distribution, etc.) exist.

Random (abstract or geometric) cell complex models. On a theoretical level,
random cell complexes in high-dimensional euclidean spaces were introduced by
[34]. This results in geometric cell complexes, i.e., cell complexes that have
an embedding and a distinction between cells that lie on the inside of the
complex and those on the outside. Moreover, to the best of our knowledge,
there is no known efficient algorithm to sample from this distribution.
Further research on random geometric cell complexes [35, 36] focused on
tesselations of low- or high-dimensional point clouds and the local topology
characterizing physical cell complexes. Such geometric graphs (or CCs) may
accurately model some real-world datasets (e.g., communication between
internet nodes) as they result in sparse, planar graphs with a possibly quite
large diameter. However, many applications have more dense, non-planar graphs
with small diameters, such as telecommunication between cell towers [11], taxi
trips (by endpoints) between neighborhoods [37], or social networks. To date,
researchers have filled the gaps in both models and sampling algorithms for
existing models by using simple lifting procedures, lifting a well-structured
graph to an abstract cell complex, or using a possibly biased sampling method.
Limiting the lifting to chordless cycles up to a certain length, for example,
makes it computationally feasible to compute all possible 2-cells (in
practice) [16]. Alternatively, cells can be sampled from the Delaunay
triangulation of a two-dimensional point cloud [24, 38]. However, these are ad
hoc constructions to provide a useful lifting for certain datasets or
synthetic data for an evaluation, respectively. These methods have geometric
properties and have not been studied in detail; they may therefore introduce
biases into the resulting data: For example, [24] uses a process that
consecutively augments triangles with neighboring triangles. This growth
process necessarily stops at the outer edges of the triangulation, making them
more likely to be part of a cell boundary than inner edges. The usage of these
ad hoc models clearly indicates the need for models of random abstract cell
complexes.

##  Appendix B Example Run on Toy Graph

This section provides an example run to give a better intuition on how the
algorithm and its optimizations work. We will be using the following graph
drawn from Erdős–Rényi ($n=8,p=0.5$):

First, we sample a uniform spanning tree (left: highlighted on graph, right:
displayed as rooted spanning tree).

To evaluate the occurence probability of
$\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}$ for all $c\in C_{T}$, we
will iterate over all edges not in $T$.

First, we calculate $\sigma(r,u),\pi(r,u)$ for all $u\in V$ using the degrees:

Then, we calculate all lowest common ancestors using Tarjan’s off-line lca
algorithm [22]. In our example, we will look at the edge $(0,3)$ with
$\text{lca}(0,3)=1$. The corresponding cycle is $c=(0,3,1,4)$.

As above, let $\gamma(n,p,l)$ denote the parts of the equation that do not
depend on any degrees of specific nodes. Recall that:

$\displaystyle\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}$
$\displaystyle=\frac{\sum_{(u,v)\in c}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\gamma(n,p,l)$ (11) $\displaystyle=\frac{2\cdot 3+3\cdot 4+4\cdot
3+3\cdot 2}{2\cdot 3\cdot 4\cdot 3}\gamma(n,p,l)=\frac{36}{72}\gamma(n,p,l)$
(12)

We can calculate this in constant time from the partials $\pi,\sigma$ along
the tree and the degrees of $u$ and $v$:

$\sigma(0,3)=\sigma(r,0)+\sigma(r,3)-2\sigma(r,lca(0,3))=34+28-2\cdot 16=30$

$\pi(0,3)=\frac{\pi(r,0)\pi(r,3)(d(lca(0,3))-1)}{\pi(r,lca(0,3))^{2}}=\frac{96\cdot
48\cdot 4}{16^{2}}=72$

$\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}=\frac{\sigma(0,3)+(d(0)-1)(d(3)-1)}{\pi(0,3)}\gamma(n,p,l)=\frac{30+3\cdot
2}{72}\gamma(n,p,l)=\frac{36}{72}\gamma(n,p,l)$ $\square$

##  Appendix C Approximation of the occurence probability $\rho_{c}$

A cycle is induced by a spanning tree if and only if all but one of its edges
are part of a spanning tree. These edges then form a path on the spanning
tree. To estimate the occurence probability of a cycle, we can add the
probabilities of each of these possible paths being included in a uniform
spanning tree.

In the following, we introduce the Laplacian Random Walk, which provides us
with another way to model the distribution of paths on the graph. From this,
we derive an exact formula to calculate the occurence probability $\rho_{c}$,
and approximate this formula using the assumption that the graph was drawn
from Erdős–Rényi.

###  C.1 The Laplacian Random Walk

For any simple (non-closed) path from $u$ to $v$, the probability of all edges
being part of a uniform spanning tree is the same probability as that of a
Loop-Erased Random Walk (LERW), which is in turn the same as the Laplacian
Random Walk (LRW) [19] from $u$ to $v$ taking that path [39].

A LERW starts at $u$ and randomly selects a neighbor until reaching $v$.
However, whenever a previously visited node $w$ is reached, this loop is
_erased_ , i.e., all nodes visited since the last visit to $w$ are removed
from the resulting walk. Note that, in practice, uniform spanning trees are
usually sampled using LERWs by Wilson’s algorithm [18].

The LRW achieves the same probability distribution as the LERW by avoiding
loops in the first place. To do this, the transition probabilities have to be
adjusted to account for the possibility of creating a loop before reaching the
target node $v$. First, nodes that were already visited are never chosen.
Second, nodes with no connection to the target node (except through the
current node or previously visited nodes) are also never chosen as the LERW
would have to return to a visited node before reaching the target node.

In every step of the LRW, the set of already visited nodes changes, thus
necessitating a recalculation of these probabilities. The probabilities can be
modeled using the Graph Laplace operator $L=D-A$: In each step $i$, Laplacian
random walk defines a function $f_{i}:V\rightarrow\mathbb{R}$ on the nodes.
For the target node $v$, it has a fixed value of $f_{i}(v)=1$. Conversely, all
nodes $w$ already visited at time $i$ have a fixed value of $f_{i}(w)=0$. For
all other nodes $w$, the probabilities are the solution to the laplace
equation $L(f_{i})(w)=0$ holds. The probability to transition from $u$ to $w$
is then $\tau^{(i)}(w)=f_{i}(w)/\sum_{x\in\text{Neigh}(u)}f_{i}(x)$.

###  C.2 Estimating the occurence probability

A spanning tree induces a cycle $c$ if and only if all but one edge of $c$ are
part of the tree. The probability of each of these paths being part of the
tree can be calculated using the laplacian random walk: For every edge $(u,v)$
in $c$, we calculate the LRW probability of the path $c\setminus\\{(u,v)\\}$.

$\rho_{c}=\sum_{(u,v)\in c}\quad\prod_{(w,x)\in
c\setminus\\{(u,v)\\}}p_{i}(w)=\sum_{(u,v)\in c}\quad\prod_{(w,x)\in
c\setminus\\{(u,v)\\}}\frac{f_{i}(x)}{\sum_{y\in\text{Neigh}(w)}f_{i}(y)}$
(13)

Since the LRW requires calculating $f_{i}$ for every step of the walk, it is
too computationally expensive for our purpose. To efficiently approximate
this, we use the expected graph for our calculations. The expected ER graph is
a weighted complete graph with a weight of $p$ on each edge. Since all nodes
that have not been visited and are not $v$ are symmetric (including weights),
their $\tilde{f}_{i}$ will be the same, meaning only the number of visited
nodes $i$ and $x$ influence this. This gives us the following estimation:

$\forall u:f_{i}(u)\approx\begin{cases}1&\text{if }u\text{ is the target}\\\
0&\text{if }u\text{ has been visited}\\\ \tilde{f}_{i}:=\frac{i\cdot 0+1\cdot
1}{i+1}=\frac{1}{i+1}&\text{else}\end{cases}$ (14)

We denote the transition probability of the laplacian random walk in step $i$
by $\tau_{c}^{(i)}$. For the first step, no other node has been visited and
all neighbors are either unvisited or $v$. Out of the $n-1$ neighbors in the
expected graph, $n-2$ are unvisited with $f_{i}\approx\hat{f}_{i}$, and one is
the target node.

$\displaystyle\tilde{\tau}_{c}^{(1)}$
$\displaystyle=\frac{\tilde{f}_{i}}{d(w)\left(\frac{n-2}{n-1}\tilde{f}_{i}+\frac{1}{n-1}\right)}$
(15)
$\displaystyle=\frac{\frac{1}{2}}{d(w)\frac{1}{n-1}\left(\frac{n-2}{2}+1\right)}$
(16) $\displaystyle=\frac{n-1}{d(w)\left(n-2+2\right)}$ (17)
$\displaystyle=\frac{1}{d(w)}\frac{n-1}{n}$ (18)

After step 1: Note that we already know that one neighbor has been visited in
the previous step, so we only need to consider the remaining $d(w)-1$
neighbors. Of these, in expectation, $\frac{i-2}{n-2}$ have been visited so
far and $\frac{1}{n-2}$ neighbors are the target node $v$. $\frac{n-i-1}{n-2}$
are unvisited.

$\displaystyle\tilde{\tau}_{c}^{(i)}$
$\displaystyle=\frac{\tilde{f}_{i}}{(d(w)-1)\frac{1}{n-2}((n-i-1)\tilde{f}_{i}+1)}$
(19)
$\displaystyle=\frac{1}{d(w)-1}\frac{(n-2)\frac{1}{i+1}}{\frac{n-i-1}{i+1}+1}$
(20) $\displaystyle=\frac{1}{d(w)-1}\frac{n-2}{n-i-1+i+1}$ (21)
$\displaystyle=\frac{1}{d(w)-1}\frac{n-2}{n}$ (22)

For the transition to $v$ (step $l-1$), we know that $v$ is a neighbor.
Therefore, there is one neighbor that was certainly visited, one that has
value 1, and of the remaining $d(w)-2$ neighbors,
$\frac{n-(l-1)-1}{n-3}=\frac{n-l}{n-3}$ have not been visited and have value
$f_{l-1}$:

$\displaystyle\tilde{\tau}_{c}^{(l-1)}$
$\displaystyle=\frac{1}{1+(d(w)-2)\frac{n-l}{n-3}f_{l-1}}$ (23)
$\displaystyle=\frac{1}{1+\frac{(d(w)-2)}{n-3}\frac{n-l}{l}}$ (24)
$\displaystyle\approx{}\frac{1}{1+\frac{(n-1)q-2}{n-3}\frac{n-l}{l}}=:\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\tau}$}}_{c}^{(l-1)}$
(25)

cycle length is $l+1$, path is $l$; $(u,v)\in c$ denotes edges

$\displaystyle\rho_{c}$ $\displaystyle\approx\sum_{(u,v)\in
c}\tilde{\tau}_{c}^{(l-1)}\tilde{\tau}_{c}^{(1)}\prod_{i=2}^{l-2}\tilde{\tau}_{c}^{(i)}$
(26) $\displaystyle=\sum_{(u,v)\in
c}\tilde{\tau}_{c}^{(l-1)}\tilde{\tau}_{c}^{(1)}(d(v^{\prime})-1)\prod_{w\in
c,u\neq w\neq v}\frac{1}{d(w)-1}\frac{n-2}{n}$ (27)
$\displaystyle=\frac{\sum_{(u,v)\in
c}\tilde{\tau}_{c}^{(l-1)}\frac{d(u)-1}{d(u)}\frac{n-1}{n}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\cdot\left(\frac{n-2}{n}\right)^{l-3}$ (28)
$\displaystyle=\frac{\sum_{(u,v)\in
c}\tilde{\tau}_{c}^{(l-1)}\frac{d(u)-1}{d(u)}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\cdot\left(\frac{n-2}{n}\right)^{l-3}\frac{n-1}{n}$ (29)
$\displaystyle\approx\frac{\sum_{(u,v)\in
c}\tilde{\tau}_{c}^{(l-1)}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\cdot\left(\frac{n-2}{n}\right)^{l-3}\frac{n-1}{n}\frac{(n-1)q-1}{(n-1)q}=:\tilde{\rho}_{c}$
(30)

Note that we approximated $\frac{d(u)-1}{d(u)}\approx\frac{(n-1)q-1}{(n-1)q}$
as this makes it easier to compute. By substituting
$\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\tau}$}}_{c}^{(l-1)}$ for
$\tilde{\tau}_{c}^{(l-1)}$, we arrive at:

$\displaystyle\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\rho}$}}_{c}:\text{}$
$\displaystyle=\frac{\sum_{(u,v)\in
c}\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\tau}$}}_{c}^{(l-1)}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\cdot\left(\frac{n-2}{n}\right)^{l-3}\frac{n-1}{n}\frac{(n-1)q-1}{(n-1)q}$
(31) $\displaystyle=\frac{\sum_{(u,v)\in
c}(d(v)-1)(d(v^{\prime})-1)}{\prod_{w\in
c}d(w)-1}\cdot\left(\frac{n-2}{n}\right)^{l-3}\frac{n-1}{n}\frac{(n-1)q-1}{(n-1)q}\tilde{\raisebox{0.0pt}[0.85pt]{$\tilde{\tau}$}}_{c}^{(l-1)}$
(32)

##  Appendix D Additional Plots

The evaluation code used to generate these plots is available at
github.com/josefhoppe/random-abstract-cell-complexes.

Figure 9: Number of simple cycles $N_{l}$ on 50 graphs sampled from
Erdős–Rényi with $n=20$, $p=0.3$. The red line indicates the a priori
estimation $\mathcal{N}_{l}$. There is a large variance in the number of cells
for a given $l$, especially as $l\rightarrow n$.

(a) Estimated Occurence Probability

(b) Approximated Occurence Probability

Figure 10: The estimated (a) and approximated (b) probability of simple cycles
to be induced by a random spanning tree on one graph sampled from ER with
$n=30,p=0.1$; cycles for evaluation obtained from $10$ random STs. Both
methods are less accurate than for $p=0.5$ (comp. Figure 6), which is expected
as the connectedness decreases and relative variance in degree increases
(i.e., the graph is much less similar to the expected graph in behavior). Even
with these challenges, the error is still less than one order of magnitude.

(a) Evaluation on the same cycles and graph sampled from ER with $n=30,p=0.5$
as Figure 6.

(b) Evaluation on the same cycles and graph sampled from ER with $n=30,p=0.1$
as Figure 10.

Figure 11: The approximation error of a hypothetical approximation that
assigns each cycle the mean probability of all cycles with the same length,
for a moderate configuration (a) and a sparse configuration (b). The
estimation error is significantly larger than either of our approaches, i.e.,
our approaches detect significantly more than just the cycle length.

(a) Homophilic SBM ($p=0.4,q=0.2$)

(b) Heterophilic SBM ($p=0.1,q=0.5$)

Figure 12: The estimated number of cycles for different lengths, number of
sampled cells, and releative error by length on 50 graphs sampled from a
homophilic (a) and heterophilic (b) SBM, each with two blocks of 10 nodes. In
both cases, the accuracy is surprisingly good considering that the
approximations assume an underlying ER-Graph. The accuracy is massively
reduced for lengths where the sampled number of cells is too small.

(a) Homophilic SBM ($n=30,p=0.4,q=0.2$)

(b) Heterophilic SBM ($n=50,p=0.2,q=0.4$)

Figure 13: The approximated occurence probability (relative to the correct
probability) for cycles on graphs sampled from the SBM. Xs mark cycles that
only include nodes from one block. Figure 14: The sampling-based estimation on
$K_{50,50}$

(a) Barabasi-Albert model with $m=3$.

(b) Configuration model, the degree for node $i$ is
$\smash{\left\lceil\frac{n}{2+i\div 2}\right\rceil}$.

Figure 15: The sampling-based estimation on graphs sampled from random graph
models with uneven degree distributions (50 graphs with $n=20$ nodes each).
While the error increases further in both cases, it is still significantly
more accurate than expected.

(a) Zachary’s Karate Club [40]

(b) November 17 terror cell network [41]

Figure 16: The estimated number of cycles for different lengths, number of
sampled cycles, and releative error by length on 50 runs sampled on two real-
world graphs. In both cases — given a reasonable number of occurring cycles —
the estimation error is within an order of magnitude, but the karate club
shows a significantly larger error. Given its very much non-ER-like structure,
this is to be expected. Figure 17: The actual number of cells is, in
expectation, $\nu$.

(a)

(b) $n=12$

Figure 18: Analysis of random cell complexes, comparing our model (RCC) to the
triangulation-based model from [24] (triangulation). (a) compares the
dimension of the 1- and 2-cohomology, showing that, in both models,
2-homologies are only rarely added significantly before all 2-cohomologies
have been filled. (b) shows what fraction of sampled CCs is orientable, again
showing a similar behavior for the two models.