On using undirected graph techniques for directed graphs through Category Theory

Abstract Many complex systems are modeled as graphs. Depending on the setting, graphs can be either directed or undirected. While many computational tools have been developed for both types of graphs, some tools only exist for undirected graphs. Thus, creating a ’bridge’ that connects directed graphs to undirected graphs would unlock the potential for using undirected graph techniques in appropriate directed graph contexts. We used Category Theory in a novel way to map a simple directed graph to a bipartite undirected graph that we call a prime graph. Formally, we show that there exists an isomorphism between the category of simple directed graphs and a category of prime graphs whose objects are labeled undirected bipartite graphs. The labeling is what gives the notion of direction to an undirected graph. By taking advantage of the isomorphism between these two categories, we extend undirected graph techniques to directed graph contexts by converting the directed graphs into prime graphs. We demonstrate this framework by applying it to the problems of network alignment and spectral graph clustering.