Extending Undirected Graph Techniques to Directed Graphs via Category Theory
Networks naturally arise in many real-world situations. They are ubiquitous across both the natural sciences and engineering. Mathematically, networks are mathematical graphs with additional features and properties on their vertices and edges. A mathematical graph is a conceptual structure consisting of a collection of nodes (properly called vertices) connected together by links (called edges). There are many important problems in various branches of mathematics that study the properties of such graphs.
But you can assign additional properties to the vertices and edges of a graph to model real-world physical things. For example, artificial neural networks that underlie machine learning and artificial intelligence tools like ChatGPT are networks that learn and represent information by adjusting the strength of the connections between the vertices — their weights. This is analogous to the synaptic weights between biological neurons in the brain, which can also be modelled and studied mathematically as networks. Such weights represent an additional ‘feature’ or property assigned to the vertices, important to that specific application. The list of such examples and applications in today’s world is almost endless.
One fundamental distinction in graph theory is whether a graph is directed or undirected. In a directed graph, the edges have a specific direction, meaning information can only travel from one vertex to another in a particular direction. In contrast, in an undirected graph, the direction of the edges is not relevant, and information can flow in both directions between vertices.
Many real-world networks are often modelled as directed graphs, which makes sense. However, many useful and important mathematical methods for calculating and studying graph properties apply only to undirected graphs. But the computational analysis of directed graphs tends to be much more mathematically challenging and restrictive. From a practical perspective, it would be very useful to analyze and solve certain classes of problems for directed graphs using adapted versions of known undirected graph methods.
In a recent paper we published in MDPI Mathematics, we tackled this problem by using notions and principles of category theory within a graph context.
Category theory studies abstract mathematical structures and their relations. These structures, or categories, are composed of a collection of things or ‘objects’ and a collection of relations between objects called ‘morphisms’. Category theory was originally developed within pure mathematics as a way of building connections between seemingly different and unrelated parts of the mathematical universe.
But more recently, category theory has been used broadly across the natural sciences and engineering, including applications to machine learning and artificial neural networks, biological networks, and social networks. See the various references in our paper that point to some of these interesting applications.
We bridge the directed graph framework to an undirected one by first constructing a category of undirected graphs that encodes the notion of direction. This category, which we call the prime graph category, has as objects undirected graphs equipped with a ‘prime labeling’ and morphisms that preserve the prime labeling. The key idea in this work is that this prime labeling provides a notion of direction over the structure of the undirected graph, allowing us to define a unique direction when transforming to directed graphs and vice versa.
With this in mind, we constructed a mathematical connection (technically, a bijective functor) that relates the category of simple directed graphs with the category of prime graphs so that the notion of direction is preserved. It is worth mentioning that one can always relate a directed graph to an undirected graph in a trivial way by simply considering the underlying structure and ‘forgetting’ the direction. This correspondence gives rise to a ‘forgetful’ functor that is not invertible. We also provide in the paper a (pseudo)algorithm to perform the prime graph transformation.
This work is the first to address the problem of converting directed graph morphisms into undirected graphs while preserving the notion of direction. This is crucial for the types of practical applications we and others are interested in, in particular, the problem of network alignment. Network alignment is a technique that allows us to compare two different networks, which is important for many real-world applications.
While several network alignment tools exist for undirected graphs, to the best of our knowledge, none exist for directed graphs.
This problem has a long history, and a number of mathematical and computational methods have approached it in different ways. Typically, such a comparison is performed by ‘putting one network on top of the other’ in such a way that the structure — or topology — between them is preserved as much as possible, followed by calculating a similarity score between the networks. While several network alignment tools exist for undirected graphs, to the best of our knowledge, none exist for directed graphs.
The approach we develop in this paper attempts to perform network alignment on directed graphs via their corresponding prime graphs (which are undirected). We empirically validated and showed our approach's efficacy by using synthetically generated pairs of networks whose pairwise similarity is known and controlled by the graph generator’s pairwise correlation coefficient. Our results show a strong statistical correspondence between the generated networks and their resulting pairwise network similarity scores. We also extended our method and improved on related (spectral) graph analysis methods that compute graph properties that partition or ‘cut’ graphs in certain ways.
