IEEE VIS 2024 Content: Structure-Aware Simplification for Hypergraph Visualization

Structure-Aware Simplification for Hypergraph Visualization



 Peter D Oliver - Oregon State University, Corvallis, United States

 Eugene Zhang - Oregon State University, Corvallis, United States

 Yue Zhang - Oregon State University, Corvallis, United States

 Room: Bayshore VII

2024-10-18T12:42:00ZGMT-0600Change your timezone on the schedule page
2024-10-18T12:42:00Z

Exemplar figure, described by caption below — We present a structure-guided simplification scheme for hypergraphs. Given an input hypergraph (left), we identify a cycle basis for its bipartite graph representation (middle). Using the basis cycles, we decompose the hypergraph into a union of topological blocks (purple bubbles), bridges, and branches (green bubbles). We apply minimal cycle collapse and cycle cut simplifications to eliminate unavoidable overlaps in the topological blocks, and apply leaf pruning simplifications to reduce the space required by bridges and branches. Our simplification prioritizes preserving long cycles, bridges, and branches so that the most significant structures are kept in the simplified results (right).

Fast forward

Full Video

Keywords

Hypergraph Visualization, Hypergraph Simplification, Hypergraph Topology, Bipartite Representation

Abstract

Hypergraphs provide a natural way to represent polyadic relationships in network data. For large hypergraphs, it is often difficult to visually detect structures within the data. Recently, a scalable polygon-based visualization approach was developed allowing hypergraphs with thousands of hyperedges to be simplified and examined at different levels of detail. However, this approach is not guaranteed to eliminate all of the visual clutter caused by unavoidable overlaps. Furthermore, meaningful structures can be lost at simplified scales, making their interpretation unreliable. In this paper, we define hypergraph structures using the bipartite graph representation, allowing us to decompose the hypergraph into a union of structures including topological blocks, bridges, and branches, and to identify exactly where unavoidable overlaps must occur. We also introduce a set of topology preserving and topology altering atomic operations, enabling the preservation of important structures while reducing unavoidable overlaps to improve visual clarity and interpretability in simplified scales. We demonstrate our approach in several real-world applications.