Evolution of (hyper)graph invariants under (hyper)graph rewritings​
​by Maurizio Moreschi
Abstract: In this project, we consider the evolution of hypergraph invariants related to complexity, symmetry and robustness in Wolfram Models. Incidentally, we provide a function for the geometric decomposition of automorphism groups of graphs, which can be useful also in other context.
​
​Goal: The main purpose of the work is identify (hyper)graph invariants whose evolution in Wolfram Models may be interesting to analyze systematically.
​
​What next?: We have identified a few aspects interesting to study more systematically, so one first step is too get the memory necessary for the systematic investigation and analyze more data. We also identify two possible directions for further research.

1. Introduction

A (hyper)graph Wolfram Model is a sequence of directed (hyper)graphs obtained by iterative application of a given (hyper)edge replacing rule starting from a given directed (hyper)graph as initial condition. The ongoing Wolfram Physics Project aims to recover the fundamental rules of physics as we know it in the computational framework of “causal invariance” Wolfram Models (see here for more details).
​
While the arguments on why this could be the right framework for the long-awaited unified theory of physics, the mathematical understanding of Wolfram models is at the present date too limited to be able to make any educated guess on which Wolfram Model effectively represents our universe. A list of possible candidates to computationally explore is available here.
​
The idea is that we should be able to recognize some features of the limiting geometry of the Wolfram Model in the universe that we experience today, the (hyper)edge rewritings taking place in an extremely small amount of time. A feature of central importance is for example dimensionality (see Chapter 4 of the online technical introduction or of the book of the project for more details).
​
The aim of this project is to analyze the evolution of some (hyper)graphs invariants in Wolfram Models, in order to identify aspects which are likely interesting to investigate more systematically (provided having sufficient memory available) .
​
In Section 2, we discuss local weak convergence for Wolfram Models (see here for background information). This is an interesting aspect because for a local weak convergent Wolfram Model, we approximate several graph theoretic properties of the states of the Wolfram Models far in the evolution by trying and study the local weak limit directly.
​
In Section 3, we initiate the study of the evolution of the symmetries in Wolfram Models. The motivation behind this comes from this paper of MacArthur et al. where a connection is established between a certain (geometric) factorization of the automorphism group of a graph and its reflection on the structure of the graph itself, and computationally investigated for the underlying graph of some real-work networks. We give a Wolfram language implementation (see the full notebook of the project for the details) of the technique described in the paper, which may very well have interesting applications beyond the context of Wolfram Models, for example to molecular computations and/or graph drawing. The function we produce is ready to be used for a more systematic investigation of the evolution of symmetries in Wolfram Models.
​
Section 4 is dedicated to the study the evolution of “robustness” in Wolfram Models via the notion of “redundancy” also considered in the paper of MacArthur et al..
​
In Section 5 and Section 6, we lay out our conclusions and ideas for further research, respectively.

2. Local Weak Convergent Wolfram Models

An important first step in order to study the limiting behaviour of Wolfram Models is to look for models which convergence in some known notion from the theory of graph limits. At the beginning of page 189 of the book of the Physics Project, it is hinted to a possible use of graphons theory, that is the graph limits theory for dense graphs. In this section, we try and give a different perspective.
​
In our setting, it is not clear a priori what a sensible measure of density could be. For each directed hypergraph we can consider the underlying directed graph obtained by identifying directed hyperedges with directed subgraphs. Since we are interested in studying the underlying geometry, we can also forget about the directness of the vertices and just consider the resulting undirected graph. Still, the graphs we obtain this way do most often have multiple edges, hence no sensible notion of density. It must also be said, though, that for our purposes multiple edges are likely not going to play a decisive role. Therefore, we can identify each multiple edge with a single one. This leads to the following definition of undirected graph “associated” to an hypergraph (note that the associated graphs can still have single loops).
In[]:=
<<IGraphM`;
In[]:=
associatedUndirectedGraph[H_?hypergraphQ]:=IGUndirectedGraph[ResourceFunction["HypergraphToGraph"][H]];
For the associated graph of an hypergraph there is a natural definition of density. We call this measure the “essential density” of the hypergraph.
In[]:=
hypergraphEssentialDensity[H_?hypergraphQ]:=Module{G=associatedUndirectedGraph[H]},
2EdgeCount[G]
VertexCount[G](VertexCount[G]+1)
;
By computing the essential hypergraph densities for the first few states of some of the notable universes from here, we immediately see a rather interesting behaviour. Namely, the essential hypergraph densities of all models seems overall decreasing in the evolution and most likely convergent to a finite quantity, which in several cases appears to be zero. If the density tends to zero, then it means that we are in sparse regime and one may hope to actually have Benjamini-Schramm (local weak) convergence (see here for background information).
Out[]=
wm11114
wm1113
wm1116
wm1137
wm1157
wm1158
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
wm1167
wm1172
wm1173
wm1194
wm1199
wm121
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
wm1218
wm12518
wm1268
wm1271
wm1277
wm1295
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
wm1316
wm1321
wm1331
wm1333
wm1334
wm1337
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
wm1348
wm1362
wm1368
wm1381
wm1428
wm1433
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
0
2
4
6
8
10
0.0
0.2
0.4
0.6
0.8
1.0
Of course, in order for the Benjamini-Schramm convergence to even make sense we need a stronger property than the asymptotic vanishing of the density. We need namely that the maximum vertex degree of the graphs in the sequence stays bounded. In the picture below, the growth of the first few steps of some notable Wolfram Models is shown.
Out[]=
wm11114
wm1113
wm1116
wm1137
wm1157
wm1158
0
2
4
6
8
10
0
2
4
6
8
10
12
0
2
4
6
8
10
0
200
400
600
800
1000
0
2
4
6
8
10
0
2
4
6
8
10
12
14
0
2
4
6
8
10
0
2000
4000
6000
8000
10000
0
2
4
6
8
10
0
2
4
6
8
10
12
0
2
4
6
8
10
0
2
4
6
8
10
wm1167
wm1172
wm1173
wm1194
wm1199
wm121
0
2
4
6
8
10
0
2
4
6
8
10
12
0
2
4
6
8
10
0
2
4
6
8
10
0
2
4
6
8
10
0
5
10
15
20
0
2
4
6
8
10
0
2
4
6
8
10
12
0
2
4
6
8
10
0
1
2
3
4
5
6
0
2
4
6
8
10
2.0
2.2
2.4
2.6
2.8
3.0
wm1218
wm12518
wm1268
wm1271
wm1277
wm1295
0
2
4
6
8
10
0
1
2
3
4
0
2
4
6
8
10
0
5
10
15
20
0
2
4
6
8
10
0
2
4
6
8
0
2
4
6
8
10
0
10
20
30
40
0
2
4
6
8
10
0
10
20
30
40
0
2
4
6
8
10
0
5
10
15
20
wm1316
wm1321
wm1331
wm1333
wm1334
wm1337
0
2
4
6
8
10
0
2
4
6
8
10
12
14
0
2
4
6
8
10
0
1
2
3
4
0
2
4
6
8
10
0
2
4
6
8
10
0
2
4
6
8
10
0
2
4
6
8
0
2
4
6
8
10
0
2
4
6
8
0
2
4
6
8
10
0
2
4
6
8
10
12
wm1348
wm1362
wm1368
wm1381
wm1428
wm1433
0
2
4
6
8
10
0
5
10
15
20
25
0
2
4
6
8
10
0
1
2
3
4
5
6
7
0
2
4
6
8
10
0
2
4
6
8
0
2
4
6
8
10
0
2
4
6
8
10
0
2
4
6
8
10
0
1
2
3
4
5
0
2
4
6
8
10
0
1
2
3
4
5
6
7
Of the models in the above picture, the growth rates which suggest a possible uniform bound on the maximum degrees of the associated graphs are the following:
In[]:=
possiblyBoundedDeg={"wm11114","wm1157","wm1172","wm121","wm1218","wm12518","wm1321","wm1333","wm1334","wm1362","wm1368","wm1381","wm1428","wm1433"};
Checking Benjamini-Schramm convergence by computing the whole expected spectral measures is computationally unfeasible. However, we know from this paper of Bordenave, Lelange and Salez that the the sequence of the relative matching numbers of the graphs in a local weak convergent sequence converges, and this last fact we can check numerically. If we do not observe convergence of the relative matching numbers, then we exclude Benjamini-Schramm convergence as well.
In[]:=
relativeMatchingNumber[H_?hypergraphQ]:=Module{G=IGUndirectedGraph[ResourceFunction["HypergraphToGraph"][H]]},
IGMatchingNumber[G]
VertexCount[G]
;
In the picture below, we plot the behaviour of the sequence of matching numbers for the models from the list above.
Out[]=
wm11114
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1157
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1172
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm121
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1218
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm12518
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1321
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1333
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1334
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1362
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1368
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
wm1381
0
2
4
6
8
10
12
0.0
0.1
0.2
0.3
0.4
0.5
From the pictures above it seems that the oscillation in the sequences of matching numbers tends to decrease along the evolution, suggesting thus that the sequences converge. These models are thus interesting to be further investigated for possible local weak convergence. Of course, following these very lines (with more memory and computational power) it is possible to do this investigation more systematically for all notable universes.

3. The Evolution of Symmetries in Wolfram Models

In this section, we investigate the evolution of symmetries in Wolfram Models. For each directed hypergraph in the Wolfram Models we consider the automorphism group of the associated undirected graph introduced in Section 2.
​
Let us first see how the order of the automorphism group evolves for a few Wolfram Models (this is always advisable to do beforehand, because the order of the automorphism group can become very large). As you can see in the picture below, several different behaviour could take place.
Out[]=
wm11114
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1113
0
2
4
6
8
0.0
4.0×
116
10
8.0×
116
10
1.2×
117
10
wm1116
0
2
4
6
8
0
2
4
6
8
wm1137
0
2
4
6
8
wm1157
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1158
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1167
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1172
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1173
0
2
4
6
8
0
5
10
15
20
25
wm1194
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1199
0
2
4
6
8
0
5
10
15
wm121
0
2
4
6
8
0
1×
35
10
3×
35
10
5×
35
10
wm1218
0
2
4
6
8
0
2
4
6
8
wm12518
0
2
4
6
8
0
5000
10000
15000
20000
25000
wm1268
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1271
0
2
4
6
8
0
10
20
30
40
50
wm1277
0
2
4
6
8
0
20
40
60
80
100
120
wm1295
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1316
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1321
0
2
4
6
8
0
2×
19
10
4×
19
10
6×
19
10
8×
19
10
1×
20
10
wm1331
0
2
4
6
8
0
1
2
3
4
wm1333
0
2
4
6
8
0
1
2
3
4
wm1334
0
2
4
6
8
0
1
2
3
4
wm1337
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1348
0
2
4
6
8
0
20
40
60
80
100
120
wm1362
0
2
4
6
8
0
5
10
15
20
25
wm1368
0
2
4
6
8
0
1
2
3
4
wm1381
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1428
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
wm1433
0
2
4
6
8
0.0
0.5
1.0
1.5
2.0
Using our new function from Appendix A.3 we can compute the geometric decomposition of the automorphism group mentioned in the introduction, together with the corresponding “symmetric” subgraphs corresponding to the various factor (for the mathematicians, by this we mean the induced subgraph generated by the supports of the subgroups in the direct product decomposition of the automorphism group).
Sometimes we have a lot isomorphic factors. In these cases, one may want to represent the factorization of the automorphism group as list of “abstract” factors and respective multiplicities.
Finally, for a more global picture of the relation between the directed product decomposition of the automorphism group and the structure of the graph itself, we can highlight (in the given graph) all the symmetric subgraphs with different colors.

4. Redundancy

The automorphism group of an undirected graph has a natural action on the set of vertices of the graph. The “redundancy” of the graph is then defined as the quotient of the number of orbits of this action minus one divided by the number of vertices of the graph. In real-word complex networks terms, the redundancy gives a measure of the “robustness” of the network, i.e. the ability to withstand failures and perturbation (see here).
​
We define the redundancy of a hypergraph to be the redundancy of its associated undirected graph.
From the plots of the evolution of the redundancy for a few Wolfram Models (see picture below) something interesting emerges. For the vast majority of models, it looks like the redundancy tends to some finite limit along the evolution of the Wolfram Model.

5. Conclusions

In Section 2, we saw that the maximum degree and matching numbers tests exclude various Wolfram Models as candidates for local weak convergence. However, several other could still be local weak convergent in principle. So this is an interesting aspect to analyze more systematically. Section 2 leads namely to the following open question.
Open Question 1
​
In Section 3, we gave examples of the data generated by new function computing the geometric decomposition of automorphism groups. A systematic analysis of symmetries would likely take a huge amount of memory, but it would certainly be interesting to pursue to some extent (for example checking the order growth first, as we did, and ignoring the models for which this grows too fast), given the connection with the structure of the graphs themselves. The take away from Section 3 is thus the following open question.
Open Question 2
​
​
Finally, we saw in Section 4 that the redundancy seems to show a convergent behaviour in Wolfram Models. This is interesting and unexpected, thus certainly worth to be investigated systematically. Therefore, Section 4 leads to the following open question.
Open Question 3

6. Further Research Directions

On top of the research questions presented in the Section 5, we would like to suggest the following two possible research lines for further research.

Dependency of Symmetries on Initial Conditions

Evolution of Partial Symmetries

The evolution of weaker notion of symmetries than the automorphism groups would also be interesting to investigate. For this one has to move from the setting of groups to the more general setting of groupoids (see here).