Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs

Paul Rosen, Mustafa Hajij, Bei Wang

Room: 106

2023-10-22T03:00:00ZGMT-0600Change your timezone on the schedule page
2023-10-22T03:00:00Z
Exemplar figure, described by caption below
We present our technique, called Mapper on Graph, which adapts the mapper construction—a popular tool from topological data analysis—to the visualization of graphs. It provides multi-scale skeletonizations of the graph from diverse perspectives. By modifying a single input parameter, namely the number of cover elements, our approach provides a multi-scale skeletonization of the input graph that emphasizes the property of interest. In the examples presented here, the visible level-of-detail is reduced as the number of elements decreases while the homology of the graph—in the form of components and tunnels—remains well persevered.
Abstract

Node-link diagrams are a popular method for representing graphs that capture relationships between individuals, businesses, proteins, and telecommunication endpoints. However, node-link diagrams may fail to convey insights regarding graph structures, even for moderately sized data of a few hundred nodes, due to visual clutter. We propose to apply the mapper construction---a popular tool in topological data analysis---to graph visualization, which provides a strong theoretical basis for summarizing the data while preserving their core structures. We develop a variation of the mapper construction targeting weighted, undirected graphs, called mapper on graphs, which generates homology-preserving skeletons of graphs. We further show how the adjustment of a single parameter enables multi-scale skeletonization of the input graph. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.