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

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 {mog}, 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.

Paul Rosen, Mustafa Hajij, and Bei Wang. Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper On Graphs. TopoInVis: Topological Data Analysis and Visualization, 2023.

@article{rosen2023mog,
  title = {Homology-Preserving Multi-scale Graph Skeletonization Using Mapper on Graphs},
  author = {Rosen, Paul and Hajij, Mustafa and Wang, Bei},
  journal = {TopoInVis: Topological Data Analysis and Visualization},
  year = {2023},
  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 {mog}, 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.}
}