This project develops a theoretical technique for "morphing" the hyperedge sets of hypergraphs, in accordance with particular symmetries among the hyperedges. The goal is to explore a notion of hypergraph morphology. In terms of the theory, by encoding an arbitrary hypergraph into a Boolean hypercube via a Boolean function, we can perform group-theoretic analyses on the hypercube. These group symmetries are permutation isometries on the hypercube, where the intuition is to consider k-arity hyperedges as analogous to k-arity faces of shapes in geometry, which guides us to consider symmetries which respect analogous (but not precisely) the same properties. This algebraic information can be used to update the hyperedge set to a new one, which is defined via a second encoding Boolean function. A given pair of hyperedges will either ascend or descend in arity to a new encoded hyperedge that either covers them or is covered by them, when they are connected by a permutation isometry. In this project, there are two main algorithmic functions at work which rely on refining or eroding the hyperedges, the former moving up in arity and the latter moving down. The theory, as well as the implementations in Wolfram language, can allow one to derive an effective morphology of hypergraphs, via smoothing or refining the hyperedge set. One can then look towards the various data structures that hypergraphs may represent, and then infer what such a morphology would mean in that context. Moreover, this project defines code that visualizes the “space” of all applications of these two functions, in the form of a multiway evolution system. These visualizations suggest that the symmetries among the hyperedges of a hypergraph are highly related to this space of all transformations of a hypergraph, and conversely that asymmetric and “rough” hypergraphs will have convoluted spaces of transformations.
Theory and Computation
Theory and Computation
Theory
Theory
To begin, the algorithms defined in this project are motivated by a number of theoretical connections between certain finite algebraic structures. These structures link in such a way that they form a theoretical bridge, in particular one in which hypergraphs can be sent across and will be transformed on the other side. These transformations are directly linked with the group theoretic information that can be collected from our hypergraph, albeit indirectly. It is simplest to think about this as a form of indirect measurement, which involves an encoding from a less "tame" structure to a more tame one. In this case, we want to take our hypergraph and encode it into a more idealized space, which will be a Boolean hypercube (equivalently a power set lattice). This hypercube has the underlying set of all n-length strings comprised of 0s and 1s . This collection of strings allows us to think of our hypercube structure dually as a finite Boolean lattice, and as a Hamming space with the hamming distance for its metric. It is also isomorphic to the power set lattice on a set of n elements, which is a fact used many times in this project to pass seamlessly from the hypercube to the power set lattice and back.
We then want to take another copy of the same hypercube, but treating it as a different domain with no encoding yet. The goal is to define a new Boolean function on this second domain, that will encode a new evolved hypergraph structure, but with the same underlying vertex set. The rules of the evolution are governed by the group-theoretic symmetries on the cube, which serve as a collection of symmetries that permute only between hyperedges or non hyperedges, only mapping same arity faces to one another, and which preserve the Hamming distance more generally. They can be thought of as moving the 0s and 1s around within a given string, but without bit flipping to change any of the binary values. The other feature of the evolution is that a subset of vertices in the power set lattice of the vertex set will be evaluated as a hyperedge in our evolved hypergraph when there exists two hyperedge subsets that it covers (meaning that in the subset inclusion sense, they are strictly below the given element by a difference of one vertex), and moreover the strings corresponding to these hyperedges must be connected by a permutation isometry. This means that the two hyperedges from the input hypergraph whose string correspondents are connected by a permutation isometry (so they must be of the same arity) have had their hyperedge status transferred to the subset they are covered by.
This notion captures the essence of the idea for this project, which is to treat symmetry as organized redundancy. These redundancies can be "smoothed over", erasing the finer grain and lower arity hyperedges and abstracting them to a hyperedge of higher arity that covers them. One can also think of moving in the other direction and considering a subset of vertices in our second domain, along with two valid hyperedges whose corresponding strings are connected by a permutation isometry, such that the given subset of vertices is covered by these two hyperedges. This is the other direction evolution can happen in, where we evolve the hyperedge set to lower arities based on the same group theoretic information and by simply inverting the covering relation. In this project, we will look at the potential reversibility of these two operations with respect to one another, as this will be highly relevant for applications.
The mathematical theory condenses down into a series of computable steps, which can be illuminated in the following (rough) pseudo algorithm:
This notion captures the essence of the idea for this project, which is to treat symmetry as organized redundancy. These redundancies can be "smoothed over", erasing the finer grain and lower arity hyperedges and abstracting them to a hyperedge of higher arity that covers them. One can also think of moving in the other direction and considering a subset of vertices in our second domain, along with two valid hyperedges whose corresponding strings are connected by a permutation isometry, such that the given subset of vertices is covered by these two hyperedges. This is the other direction evolution can happen in, where we evolve the hyperedge set to lower arities based on the same group theoretic information and by simply inverting the covering relation. In this project, we will look at the potential reversibility of these two operations with respect to one another, as this will be highly relevant for applications.
The mathematical theory condenses down into a series of computable steps, which can be illuminated in the following (rough) pseudo algorithm:
These first three steps illustrate the primary mathematical structures used in this bridge, where the lambda mappings denote the Boolean algebra isomorphisms which allow one to pass back and forth between subsets of vertices and strings of the hypercube.
The next two steps involve the definition of the first Boolean function, that essentially acts as an indicator function as to whether or not a particular string is encoded as a hyperedge. Specifically, the preimage is the desired sub-collection of strings to compute that indicate hyperedges.What we can now do is use the generic symmetric group on the numbers 1 through n to directly define permutations on the hypercube itself, in terms of the permutation actions on this set of numbers.One can think about this as a shuffling of the 0s and 1s of a given string based on the action of the underlying permutation on the set of indices, which will always preserve the “bit distance” (Hamming distance) on the hypercube. These are permutation isometries, which can be used to define interesting group actions on the strings of the hypercube. In particular, we want to identify a sub-collection of these permutation isometries that fix the values of certain string entries as invariant, and map hyperedges to hyperedges or non-hyperedges to non-hyperedges.This step reflects the computation of the group action on each ultrafilter, where the ith ultrafilter can be thought of as the collection of all strings with a 1 value in the ith entry. In visual terms, it can be seen as a maximal sub-hypercube of the overall hypercube. The chain of subgroups essentially restricts from the isometry group of the hypercube to the image of the stabilizer subgroup of the number i, via the group embedding from the symmetry group on the numbers 1 through n into said isometry group, and then lastly to a subgroup of the stabilizer which only permutes between strings encoded as hyperedges or non-hyperedges.The new Boolean function on the copy of the hypercube is defined per ultrafilter-specifically per component function corresponding to each ultrafilter, which serves as the most important definition of the transformation. Mainly, we can see that an element in the particular ultrafilter (in our second "blank" copy of the hypercube) is evaluated as a hyperedge in our output hypergraph when there exist two elements covered by it that are connected by a permutation isometry, as well as both being hyperedges. Thus, this gives us a refinement of the hyperedge set to hyperedges of higher arity.This is the definition of the upwards evolution of the hyperedges via the algebraic information. We can also think of the opposite process, where we modify the existence criteria to demand two elements that instead cover our given element, as well as being hyperedges and connected by a permutation. This gives us an erosion of the hyperedge set, breaking it into discrete parts.Lastly, we define the primary Boolean function that evaluates a string to encode a hyperedge of our new hypergraph when there exists at least one ultrafilter and component function that evaluates our string as a true (as a hyperedge). From here, we can define the same lambda functions to convert from the preimage of our new Boolean function to the new output hypergraph.
Computation
Computation
To implement this morphological schematic into Wolfram language, the focus shifts more towards pragmatic handling of the elements of the various algebraic structures, and less about realizing them directly. In the code that will follow, we have a "refine function" to smooth the hypergraph, and an "erosion" function to discretize the hypergraph. They both construct the ultrafilters directly from the unit strings, compute the Hi subgroups that consist of the special permutation isometries, define the updated Boolean functions with the necessary criteria, but move in opposite directions in terms of the arity evolution.
Here is a basic example of a hypergraph being separately refined and eroded, first the former then the latter:
Here is a basic example of a hypergraph being separately refined and eroded, first the former then the latter:
In[]:=
g1=Hypergraph[{1,2,3,4,5,6,7,8,9,10},{{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7},{6,7,8},{7,8,9},{8,9,10},{9,10,1},{10,1,2},{1,3,5,7,9},{2,4,6,8,10}}];Print[HypergraphPlot[g1,VertexLabels->"Name",ImageSize->400]];Print[HypergraphPlot[RefineHypergraph[g1],VertexLabels->"Name",ImageSize->400]];Print[HypergraphPlot[ErodeHypergraph[g1],VertexLabels->"Name",ImageSize->400]];
HypergraphPlot
,VertexLabelsName,ImageSize400
HypergraphPlot
,VertexLabelsName,ImageSize400
Now that we have covered the two basic mechanisms, we are ready to see things on a broader level, as the real interesting part of the refining and eroding is the multiplicity of applying both of them to a given hypergraph. We can consider the “space” of all transformations on an input hypergraph, and visualize it with a multiway evolution graph. The unique states will be the hypergraphs at different points in sequences of applications of both transformations, and the arrows will represent our refinement and erosion transformations. We will define an arrow in our multiway evolution system as a shade of blue if it increases the arity of the hyperedge set (specifically increasing the arity of the most frequently occurring hyperedge via the transformation), and as a shade of red if it decreases the arity of the hyperedge set (specifically decreasing the arity of the most frequently occurring hyperedge). Note that the darkest shade of blue/red depicted for an arrow will denote a transformation that transforms arity by precisely one jump up or down. Also, rather trivially, all refinements are represented by shaded blue arrows and all erosions are represented by shaded red arrows, by definition of the arity changes. However, the shades of blue and red will allow us to distinguish the transformations that morph between two more similar hypergraphs and more two different ones, in terms of the hyperedge set. For instance, a node that has a very large arity jump-thus a faint arrow-will be more different to then node it is connected with than if it were a smaller arity jump. Regarding one other detail, the hypergraph with an empty hyperedge set will be denoted by a darker grey node. Most nodes will have very faint arrows pointing to this one because most will have a large difference in arity.
I set the steps at arbitrarily-selected values to get a good idea of the nature of the multiway evolution graph, but technically you can set the steps as you wish, depending on how many transformed hypergraphs you want to be in the graph, as well as the number of explored transformations. You can also hover your cursor over the nodes of the multiway evolution graphs to see what the hypergraph at a particular point (this can only be done in a Mathematica notebook). Here are some interesting examples of this process:
Now that we have covered the two basic mechanisms, we are ready to see things on a broader level, as the real interesting part of the refining and eroding is the multiplicity of applying both of them to a given hypergraph. We can consider the “space” of all transformations on an input hypergraph, and visualize it with a multiway evolution graph. The unique states will be the hypergraphs at different points in sequences of applications of both transformations, and the arrows will represent our refinement and erosion transformations. We will define an arrow in our multiway evolution system as a shade of blue if it increases the arity of the hyperedge set (specifically increasing the arity of the most frequently occurring hyperedge via the transformation), and as a shade of red if it decreases the arity of the hyperedge set (specifically decreasing the arity of the most frequently occurring hyperedge). Note that the darkest shade of blue/red depicted for an arrow will denote a transformation that transforms arity by precisely one jump up or down. Also, rather trivially, all refinements are represented by shaded blue arrows and all erosions are represented by shaded red arrows, by definition of the arity changes. However, the shades of blue and red will allow us to distinguish the transformations that morph between two more similar hypergraphs and more two different ones, in terms of the hyperedge set. For instance, a node that has a very large arity jump-thus a faint arrow-will be more different to then node it is connected with than if it were a smaller arity jump. Regarding one other detail, the hypergraph with an empty hyperedge set will be denoted by a darker grey node. Most nodes will have very faint arrows pointing to this one because most will have a large difference in arity.
I set the steps at arbitrarily-selected values to get a good idea of the nature of the multiway evolution graph, but technically you can set the steps as you wish, depending on how many transformed hypergraphs you want to be in the graph, as well as the number of explored transformations. You can also hover your cursor over the nodes of the multiway evolution graphs to see what the hypergraph at a particular point (this can only be done in a Mathematica notebook). Here are some interesting examples of this process:
Concluding Remarks
Concluding Remarks
The merit of developing these functions and the underlying theory is on the one hand to develop meaningful operations on hypergraphs that seem analogous to morphological-type operations in terms of transforming the hyperedge set.
This sets the theoretical groundwork for precise manipulations of hyperedges to evolve to either higher arity or lower arity sets, via the combinatorial and set-theoretic covering relations and the group-theoretic information. These visualized examples reflect the non-triviality of applying iterations of the operation and seeing what happens. With more computing power and more efficiency in the actual code, one could imagine manipulating hypergraphs of much larger complexity, for applied purposes. Since hypergraphs are such a versatile modeling tool, there are many possible avenues of applied exploration.
As a simple example, we could consider a hypergraph encoding a colored image, where the given arity of hyperedges represent different color pixels on the spectrum from black pixels (regular edges) up to a white pixel (an n-face hyperedge). Perhaps the hyperedges in between correspond to the various shades between black and white. Then, the refining or eroding would just be manipulating the forms and the color of the image. This is a simplified example, but there could be much to discover in terms of image analysis and computer graphics alone.
Furthermore, the code for visualizing the actual space of possible morphological-like transformations for a given hypergraph offers direct insight into the symmetries among the initial hyperedge set, as well as certain specific paths of evolution that are of interest.
On the mathematical side of things, deriving more results about these theoretical mechanisms as transformations could lead to much more direct and immediately obvious use cases, if more relationships between these two operators were to be teased out. Perhaps this project touches on deeper ties to a homotopy of hypergraphs, which corresponds to analogous homology and cohomology theories. In any case, the branches to explore here are numerous in both potential new theory and applications.
This sets the theoretical groundwork for precise manipulations of hyperedges to evolve to either higher arity or lower arity sets, via the combinatorial and set-theoretic covering relations and the group-theoretic information. These visualized examples reflect the non-triviality of applying iterations of the operation and seeing what happens. With more computing power and more efficiency in the actual code, one could imagine manipulating hypergraphs of much larger complexity, for applied purposes. Since hypergraphs are such a versatile modeling tool, there are many possible avenues of applied exploration.
As a simple example, we could consider a hypergraph encoding a colored image, where the given arity of hyperedges represent different color pixels on the spectrum from black pixels (regular edges) up to a white pixel (an n-face hyperedge). Perhaps the hyperedges in between correspond to the various shades between black and white. Then, the refining or eroding would just be manipulating the forms and the color of the image. This is a simplified example, but there could be much to discover in terms of image analysis and computer graphics alone.
Furthermore, the code for visualizing the actual space of possible morphological-like transformations for a given hypergraph offers direct insight into the symmetries among the initial hyperedge set, as well as certain specific paths of evolution that are of interest.
On the mathematical side of things, deriving more results about these theoretical mechanisms as transformations could lead to much more direct and immediately obvious use cases, if more relationships between these two operators were to be teased out. Perhaps this project touches on deeper ties to a homotopy of hypergraphs, which corresponds to analogous homology and cohomology theories. In any case, the branches to explore here are numerous in both potential new theory and applications.
Acknowledgments
Acknowledgments
Thank you to my mentors Xerxes D. Arsiwalla and Hatem Elshatlawy for making this research experience a joy and for providing wisdom and guidance throughout the whole process. Also, thank you to Dugan Hammock for working through the geometric features of the problem with me and helping me get a firmer grasp on the implementation. Lastly, thank you to all the students of the program for such wonderful conversations, to the rest of the mentors and staff for their incredible hard work, and of course to Stephen Wolfram for making it all happen.
References
References
1
.De Winter, S., & Korb, M. (2016). Weak isometries of the Boolean cube. Discrete Mathematics, 339(2), 877–885. https://doi.org/10.1016/j.disc.2015.10.006
Cite This Notebook
Cite This Notebook